同乐学堂1.散列 hashing
2.散列码
3.处理冲突
3.1.线性探测开发定址
3.2.二次探测开放定址
3.3.双散列开放定址
3.4.链地址
4.使用散列的词典实现
|
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
public class HashedDictionary<K, V> implements DictionaryInterface<K, V>, Serializable { private TableEntry<K, V>[] hashTable; // 词典元素 private int numberOfEntries; private int locationsused; // 表位置不为null private static final int DEFAULT_SIZE = 101; // 必须为素数 public HashedDictionary() { this(DEFAULT_SIZE); } public HashedDictionary(int tableSize) { int primeSize = getnextPrime(tableSize); hashTable = new TableEntry[primeSize]; numberOfEntries = 0; locationsused = 0; } public class TableEntry<S, T> implements Serializable { private S key; private T value; private boolean inTable; // 如果元素在散列表中则为true private TableEntry(S searchKey, T dataValue) { key = searchKey; value = dataValue; inTable = true; } } public V add(K key, V value) { // 将一个新的键-值元素插入词典，如果key已在词典中，则返回与对应的值并用value替换词典中这个值 V oldValue; // 待返回的值 // 散列表太满 if (isHashTableTooFull()) rehash(); int index = getHashIndex(key); // 检查冲突并解决（这一步可能改变nindex） index = probe(index, key); // 检查并处理冲突 // Assertion:index在hashTable的合法范围内 assert (index >= 0) && (index < hashTable.length); // key未找到 if ((hashTable[index] == null) || hashTable[index].isRemoved()) { // key未找到，于是插入新元素 hashTable[index] = new TableEntry<K, V>(key, value); numberOfEntries++; locationsused++; oldValue = null; } else { // key已找到，取得旧的值以便返回，然后替换之 oldValue = hashTable[index].getValue(); hashTable[index].setValue(value); } return oldValue; } private void rehash() { TableEntry<K, V>[] oldTable = hashTable; int oldSize = hashTable.length; int newSize = getnextPrime(oldSize + oldSize); hashTable = new TableEntry[newSize]; // 增加的数组长度 // 将词典元素从旧数组重新散列到新的更大的数组，跳过null位置与已删除的元素 for (int index = 0; index < oldSize; index++) { if ((oldTable[index] != null) && oldTable[index].isIn()) add(oldTable[index].getKey(), oldTable[index].getValue()); } } private int probe(int index, K key) { // 查找从index开始的探测序列。返回含有key的元素的索引，或者返回散列表中一个可用的索引 boolean found = false; int removedStateIndex = -1; // 第一个处于已删除状态的位置的索引 // key未找到并且hashTable[index]不是null while (!found && (hashTable[index] != null)) { // hashTable[index]引用了词典的一个元素 if (hashTable[index].isIn()) { if (key.equals(hashTable[index].getKey())) found = true; else // 遵循探测顺序，index = 下一个探测索引 index = (index + 1) % hashTable.length; // 线性探测 } else { // 跳过已删除的元素，hashTable[index]引用了下一个已删除的元素 // 是第一个已删除的元素 if (removedStateIndex == -1) removedStateIndex = index; index = (index + 1) % hashTable.length; // 线性探测 } } // key已找到或者未遇到已删除的元素 if (found || (removedStateIndex == -1)) return index; // key的索引或null else // 第一个已删除元素的索引 return removedStateIndex; // 可用位置的索引 } public V getValue(K key) { V result = null; // 如果给定的查找键在词典中，则返回与之相关联的值，否则返回null int index = getHashIndex(key); // 在从hashTable[index]开始的探测序列中查找key index = locate(index, key); // key被找到 if (index != -1) result = hashTable[index].getValue(); // key已找到，取得值 return result; } public V remove(K key) { V removedValue = null; // 给定查找键，从词典中删除特定元素，返回与查找键挂念的值，如果不存在则返回null int index = getHashIndex(key); // 在从hashTable[index]开始的探测序列中查找key index = locate(index, key); // key被找到 if (index != -1) { // key已找到，将元素标记为已删除并返回它的值 removedValue = hashTable[index].getValue(); hashTable[index].setToRemove(); numberOfEntries--; } return removedValue; } private int locate(int index, K key) { boolean found = false; // 返回含有key的元素的索引，入股哦不存在这样的元素则返回-1 while (!found && (hashTable[index] != null)) { // 引用一个在词典中并且含有key的元素 if (hashTable[index].isIn() && key.equals(hashTable[index].getKey())) found = true; // key已找到 else // 沿着探测序列继续，index = 下一个探测索引 index = (index + 1) % hashTable.length; // 线性探测 } int result = -1; // key已找到 if (found) result = index; return result; } // 为词典提供迭代器 private class KeyIterator implements Iterator<K> { private int currentIndex; // 散列表中当前位置 private int numberLeft; // 迭代中剩下的元素个数 private KeyIterator() { currentIndex = 0; numberLeft = numberOfEntries; } public boolean hasNext() { return numberLeft > 0; } public K next() { K result = null; if (hasNext()) { // 寻找下一个元素的索引 while ((hashTable[currentIndex] == null) || hashTable[currentIndex].isRemoved()) currentIndex++; result = hashTable[currentIndex].getKey(); numberLeft--; currentIndex++; } else throw new NoSuchElementException(); return result; } public void remove() { throw new UnsupportedOperationException(); } }} |
5.Java类库：类HashMap
|
1
2
3
4
5
6
7
8
|
public class HashMap<K, V> { public HashMap() { } public HashMap(int initialSize) { } public HashMap(Map<? extends K, ? extends V> table) { }} |
微信扫一扫，打赏作者吧～
