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

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

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

1
2
3
4
5
interface HashTable<T1,T2> {
    public  boolean  push(T1 x, T2 y);
    public  boolean delete(T1 x);
    public  T2  get (T1 x);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Pair<T1,T2> {
    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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.ArrayList;

public class ChainHashTable<T1, T2> extends HashMaker<T1> implements HashTable<T1, T2> {
    private ArrayList<Pair<T1, T2>>[] 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<Pair<T1, T2>>();
            n = 0;
        }
        for (int i = 0; i < n; i++) {
            if (table[h].get(i).getKey() == x) {
                table[h].set(i, new Pair<T1, T2>(x, y));
                return false;
            }
        }
        table[h].add(new Pair<T1, T2>(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.

1
2
3
4
5
6
public class HashMaker<T> {
    public int returnHash(T x)
    {
        return x.hashCode();
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Arrays;

public abstract class OpenAddressHashTable<T1, T2> extends HashMaker<T1> implements HashTable<T1, T2> {
    private Pair<T1, T2>[] 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<T1, T2>(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<T1, T2>(x, y);
                    return true;
                }
            }
            return false;
        } catch(NullPointerException e) {
            table[h] = new Pair<T1, T2>(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;
        }
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        HashTable<String, String> table = new ChainHashTable<String, String>();
        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++