哈希表

什么是哈希表

哈希表,又叫散列表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希冲突的常用解决方法

链地址法(拉链法)
开放寻址法
再哈希法

具体实现代码(具体的细节问题看注释)

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package HashTable;

import java.util.TreeMap;

/**
* @ Description: 哈希表的实现
* @ Date: Created in 11:16 24/07/2018
* @ Author: Anthony_Duan
*/
public class HashTable<K extends Comparable<K>, V> {


/**
* 哈希表的长度最好是素数并且原理2的幂,这样可以解决在模的结果中出现过多的哈希冲突
* 下面是一个素数表 最后一个接近int值的最大上限
*/
private final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

//最高冲突率
private static final int upperTol = 10;
//最低冲突率
public static final int lowerTol = 2;
private int capacityIndex = 0;


private TreeMap<K, V>[] hashtable;
private int size;
//当前HashTable对象的长度
private int M;

public HashTable() {
//初始化的长度是素数表中的0号索引对应的值
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for (int i = 0; i < M; i++) {
//每一个HashTable映射表中的元素都对应的为一个红黑树存放冲突值 链地址法
hashtable[i] = new TreeMap<>();
}
}

private int hash(K key) {

/**
* 0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111
* & 0x7fffffff 是为了让结果始终为正数 这样求模不会有错误
*/
return (key.hashCode() & 0x7fffffff) % M;
}

public int getSize() {
return size;
}


public void add(K key, V value) {

TreeMap<K, V> map = hashtable[hash(key)];
//如果找到了就更新value
if (map.containsKey(key)) {
map.put(key, value);
} else {//如果没有找到就添加 并且维护size
map.put(key, value);
size++;

/**
* 如果冲突率过高 就扩容
* 这里 size >= upperTol * M 这种写法是为了避免除法
* 因为除法得出的结果为浮点型 在比较的时候整形会先转化为浮点型 这个操作其实是无用的
*/
if (size >= upperTol * M && capacityIndex + 1 < capacity.length) {
capacityIndex++;
resize(capacity[capacityIndex]);
}
}
}

private void resize(int newM) {
TreeMap<K, V>[] newHashTable = new TreeMap[newM];
for (int i = 0; i < newM; i++) {
newHashTable[i] = new TreeMap<>();
}

int oldM = M;
this.M = newM;
for (int i = 0; i < oldM; i++) {
TreeMap<K, V> map = hashtable[i];
for (K key :
map.keySet()) {
newHashTable[hash(key)].put(key, map.get(key));
}
}

this.hashtable = newHashTable;
}

public V remove(K key) {
V ret = null;
TreeMap<K, V> map = hashtable[hash(key)];
if (map.containsKey(key)) {
ret = map.remove(key);
size--;

//哈希表的动态空间处理 如果冲突率低于下限
if (size < lowerTol * M && capacityIndex - 1 >= 0) {
capacityIndex--;
resize(capacity[capacityIndex]);
}
}
return ret;
}

public void set(K key, V value) {
TreeMap<K, V> map = hashtable[hash(key)];
if (!map.containsKey(key)) {
throw new IllegalArgumentException(key + " doesn't exist!");
}
map.put(key, value);
}

public boolean contains(K key) {
return hashtable[hash(key)].containsKey(key);
}

public V get(K key) {
return hashtable[hash(key)].get(key);
}
}
-------------End Of This ArticleThank You For Reading-------------