Хэш-таблицы(реализация на языке Java)

Java   27 июля 2012  Автор статьи:  

Здесь будут приведены два возможный вида реализаций структуры типа HashMap на языке Java.
Для начала приведем базовый интерфейс HashTable:

interface HashTable {
public boolean push(T1 x, T2 y);
public boolean delete(T1 x);
public T2 get (T1 x);
}

Здесь Т1 — тип ключа, а T2 — тип значения. То, что должна делать каждая операция очевидно.
Для хранения элементов будем использовать обычный массив и структуру ArrayList. Они будут содержать элементы вида Pair:

public class Pair {
private final T1 key;
private final T2 value;
private boolean deleted;

public Pair(T1 key, T2 value) {
this.key = key;
this.value = value;
this.deleted = false;
}
public T1 getKey() {
return key;
}

public T2 getValue() {
return value;
}

public boolean isDeleted() {
return deleted;
}

public boolean deletePair(){
if (!this.deleted){
this.deleted = true;
return true;
}else{
return false;
}
}
}

Здесь флаг Deleted и связанные с ним операции добавлены для удобной работы с хэш-таблицами, реализованных с помощью открытой адресации, о которых будет сказано дальше.
1ый способ реализации — использование метода цепочек, который реализован в абстрактном классе ChainHashTable:

import java.util.ArrayList;

public class ChainHashTable extends HashMaker implements HashTable {
private ArrayList>[] table;

public ChainHashTable() {
table = new ArrayList[100000];
}

public boolean push(T1 x, T2 y) {
int h = returnHash(x);
int n;
try{
n = table[h].size();
}catch (NullPointerException e){
table[h] = new ArrayList>();
n = 0;
}
for (int i = 0; i < n; i++) { if (table[h].get(i).getKey() == x) { table[h].set(i, new Pair(x, y));
return false;
}
}
table[h].add(new Pair(x, y));
return true;
}

public boolean delete(T1 x) {
int h = returnHash(x);
int n;
try {
n = table[h].size();
} catch (NullPointerException e) {
return false;
}
for (int i = 0; i < n; i++) { if (table[h].get(i).getKey().equals(x)) { table[h].remove(i); return true; } } return false; } public T2 get(T1 x) { int h = returnHash(x); int n; try { n = table[h].size(); } catch (NullPointerException e){ return null; } for (int i = 0; i < n; i++) { if (table[h].get(i).getKey().equals(x)) { return table[h].get(i).getValue(); } } return null; } }

Здесь абстрактный класс HashMaker содержит единственную функцию ReturnHash, реализация которой указывается непосредственно при создании объекта класса ChainHashTable.

public class HashMaker {
public int returnHash(T x)
{
return x.hashCode();
}
}

2ой способ реализации - использование открытой адресации, который реализован в абстрактном классе OpenAddressHashTable:

import java.util.Arrays;

public abstract class OpenAddressHashTable extends HashMaker implements HashTable {
private Pair[] table;

public OpenAddressHashTable() {
table = new Pair[100000];
System.out.println(Arrays.toString(table));
}

public OpenAddressHashTable(int m) {
table = new Pair[m];
System.out.println(Arrays.toString(table));
}

public boolean push(T1 x, T2 y) {
int h = returnHash(x);
int i=0;
try{
if (table[h].isDeleted() ) {
table[h] = new Pair(x, y);
return true;
}
for (i = h + 1; i != h; i = (i + 1) % table.length) {
if (table[i].isDeleted() || table[i].getKey() == x) {
table[i] = new Pair(x, y);
return true;
}
}
return false;
} catch(NullPointerException e) {
table[h] = new Pair(x, y);
return true;
}
}

public boolean delete(T1 x) {
int h = returnHash(x);
try{
if (table[h].getKey() == x) {
table[h].deletePair();
return true;
}
for (int i = h + 1; i != h; i = (i + 1) % table.length) {
if (table[i].getValue() == x && !table[i].isDeleted()) {
table[i].deletePair();
return true;
}
}
return false;
} catch (NullPointerException e){
return false;
}
}

public T2 get(T1 x) {
int h = returnHash(x);
try{
if (table[h].getKey() == x && !table[h].isDeleted()) {
return table[h].getValue();
}
for (int i = h + 1; i != h; i = (i + 1) % table.length) {
if(table[i].getValue() == x && !table[i].isDeleted()) {
return table[h].getValue();
}
}
return null;
}catch(NullPointerException e){
return null;
}
}
}

Подробнее о каждой реализации вы можете узнать в этой статье.
Пример вызова:

public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
HashTable table = new ChainHashTable();
for(int i = 0; i < n;i++) { String s = in.next(); if(s.equals("push")) { String temp = in.next(); table.push(temp, temp); } if(s.equals("delete")) { String temp = in.next(); table.delete(temp); } if(s.equals("get")) { String temp = in.next(); System.out.println(table.get(temp)); } } } }

Научиться программировать

  • на Delphi

  • на Java

  • на C++