数据结构之散列表_以数据元素关键字key本身或它的线性函数作为其哈希地址,这种方法是

散列表

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

散列表的结构如下

散列表使用关键字key的值直接访问记录，加快访问速度

比如：
1 使用哈希表作为java程序和数据的缓存层，将经常使用无需向数据库插入的数据放入哈希表中，提高对数据的访问能力。降低数据库的负载压力
2 数据字典；微信通讯录右边的搜索索引

优点：一对一的查找效率很高； 可以提供快速的插入操作和查找操作

缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。

散列表的映射函数即散列函数时是散列表获取存储位置的一个关键，常用的散列函数有6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

散列函数构造方法

A 直接定址法

以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k 或 H（k）=a×k+b ； (其中a,b为常数)

优点：简单、均匀，不会产生冲突

缺点：需要知道关键字的分布，现实中不常用

适合查找表较小并且连续的情况。

B 数字分析法

是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法当关键键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。适用于关键字位数比哈希地址位数大，且关键字已知。

C 平方取中法

如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。

比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为key 。
这种方法适合事先不知道数据并且数据长度较小的情况

D 折叠法

如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址 比如key=123 456 789我们可以存储在61524，取末三位，存在524的位置
该方法适用于数字位数较多且事先不知道数据分布的情况

E 除留余数法—用的较多

• H（key）=key MOD p （p<=m m为表长）p一般为质数
• 很明显，如何选取p是个关键问题。
  p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）

F 随机数法 H（key） =Random（key） 取关键字的随机函数值为它的散列地址.当 key 的长度不等时，采用这种方法比较合适

Hash函数设计需

1.散列函数不能太复杂
2.关键字的长度
3.关键字分布是否均匀，是否有规律可循
4.尽量减少冲突
1
2
3
4

好的散列函数=计算简单+分布均匀（计算得到的散列地址分布均匀）

哈希冲突的解决方案

再好的散列函数也无法避免散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。

hash函数解决冲突的方法有以下几个常用的方法

一 开放定制法

首先有一个H（key）的哈希函数
如果H（key1）=H（key）–哈希冲突了
那么key存储位置 Hi(key) = (H(key)+di)MOD m(表长) i=1,2,3,4…k(k<=m-1)

其中di 可以取三种模式

线性探测再散列

在找到查找位置的index的index-1，index+1位置查找，index-2，index+2查找，依次类推。这种方法称为线性再探测。
只要哈希表没有被填充满，保证能找到一个空的地址存放冲突的元素
比如：m=10, H(key)=1位置冲突了，则先取di=d1=1; 则H(key)=（1+1）%10=2
如果H(key)=2还冲突则取di=d2=2,在H(key)=（2+2）%10=4 …直到不冲突为止

平方探测再散列

线性探测再散列 类似，只不过di=1^ 2 ，-1^ 2 ， 2^ 2 ， -2^2…

随机探测在散列（双探测再散列）

在查找位置index周围随机的查找。称为随机在探测。
此时 di=伪随机数序列
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

二 链式地址（也叫拉链法）

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

散列表查找原则

1. 根据哈希函数计算哈希值，如果此位置为空，则查找失败

2. 如果地址不为空，比较查找值与地址值上的关键字，如果相同则查找成功，不相同则继续根据线性探测冲突的方法继续比较下一个
   直到找到或者扫描表结束为止

散列表的实现

使用数组+链表简单实现散列表的增删改查，以及扩容，熟悉散列表的结构及原理

public class HashTable<K,V>  {

    private  int defaultSize=4;//默认桶位大小

    private  int count;//桶位中所有元素个数
    private Node<K, V>[] hashTable;

    public static void main(String[] args) {

        HashTable<Integer,String> hashTable = new HashTable<>();
        hashTable.putValue(10 , "jack");
        hashTable.putValue(11 , "leo");
        hashTable.putValue(22, "ko");
        hashTable.putValue(66, "jrSmith");
        hashTable.putValue(36,"james");


        hashTable.printTable();

        System.out.println(hashTable.setKey(66, "james"));
        System.out.println(hashTable.setKey(11, "bens"));
        System.out.println(hashTable.deleteKey(22));
        System.out.println("-------------------");
        System.out.println(hashTable.getValue(11));
        hashTable.printTable();
    }

    public  HashTable( ){
        hashTable=  new Node[defaultSize];
    }

    public  HashTable(int size){
        this.defaultSize = size<=0 ?this.defaultSize : size;
        hashTable=  new Node[this.defaultSize];
    }

    private  int hash(K key){


        return  key.hashCode()%(defaultSize=hashTable.length);
    }

    private static class  Node<K, V>{
        final K key;
        V value;
        Node<K,V> next;
        final int hash;
         Node(K key, V value, int hash, Node<K,V> next) {
             this.key = key;
             this.value = value;
             this.hash = hash;
             this.next=next;
         }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }


    /*
     * @param: [key, value]
     * @return: void
     * @author: Jerssy
     * @dateTime: 2021/3/26 11:26
     * @description:增
     */
    public void putValue(K key, V value){
          int tableHash;
          Node<K, V> currentNode;Node<K, V> replaceNode = null;
          if (key==null){
              return;
          }

          if ((currentNode=hashTable[tableHash=hash(key)]) == null) {//如果当前桶位null
             hashTable[tableHash]=new Node<>(key, value,key.hashCode(),null);

         }
         else if (currentNode.hash==tableHash||key.equals(currentNode.key)){//当前桶hash与key hash相同或者不同但equal相等
              replaceNode=currentNode;
         }
         else {
                if (currentNode.next==null){//当前桶位只有一个将此节点放入链表尾部
                    currentNode.next=new Node<>(key, value, key.hashCode(), null);

                }
                else {
                    Node<K, V>  node=currentNode; boolean isReplace=false;
                    while (node.next != null) {
                         if (node.hash==tableHash||key.equals(node.key)) {//链表中存在相同值的节点需要替换
                             isReplace=true;
                             replaceNode=node;
                             break;
                         }
                         node=node.next;
                    }
                   if (!isReplace) node.next = new Node<>(key, value, key.hashCode(), null);//只有value值不相同的时候才放入链表尾部
                }

         }

         if (replaceNode!=null&&value != null){
              replaceNode.value = value;
         }

        float loadFactor = 0.75f;

        if (++count>= loadFactor *defaultSize){
           hashTable= resize();
        }
    }

    /*
     * @param: [key]
     * @return: V
     * @author: Jerssy
     * @dateTime: 2021/3/26 11:26
     * @description: 查
     */
    public V getValue(K key){

        int keyHash=hash(key);
        Node<K, V> tableBucket;
        if (hashTable[keyHash]!=null){
            if ((tableBucket=hashTable[keyHash]).hash==keyHash){
                return  tableBucket.value;
            }
            else {
                Node<K, V> node=tableBucket;
                while (node != null){
                    if (node.hash==keyHash||key.equals(node.key)){
                        return node.value;
                    }
                    node=node.next;
                }
            }
        }
        return null;
    }

    /*
     * @param: [key, value]
     * @return: boolean
     * @author: Jerssy
     * @dateTime: 2021/3/26 11:26
     * @description: 改
     */
    public boolean setKey(K key,V value){

        int keyHash=hash(key);
        Node<K, V> tableBucket;
        if (hashTable[keyHash]!=null){
            if ((tableBucket=hashTable[keyHash]).hash==keyHash){
                tableBucket.value = value;
                return true;
            }
            else {
                Node<K, V> node=tableBucket;
                while (node != null){
                    if (node.hash==keyHash||key.equals(node.key)){
                        node.value = value;
                        return true;
                    }
                    node=node.next;
                }
            }
        }
        return false;
    }

    /*
     * @param: [key]
     * @return: V
     * @author: Jerssy
     * @dateTime: 2021/3/26 11:27
     * @description:删
     */
    public  V deleteKey(K key){

        int keyHash=hash(key);V oldValue;
        Node<K, V> tableBucket,deleteKeyNode = null;  Node<K, V> node = null;

        if (hashTable!=null&&defaultSize>0&&(tableBucket=hashTable[keyHash])!=null){
            if (tableBucket.hash == keyHash||tableBucket.key.equals(key)){
                deleteKeyNode=tableBucket;
            }
            else {
                if (tableBucket.next!=null){

                    node=tableBucket;
                    while (node!= null){
                        if (node.hash==keyHash||key.equals(node.key)){
                            deleteKeyNode = node;
                            break;
                        }
                        node=node.next;
                    }
                }
            }

            if (deleteKeyNode != null){
                oldValue=deleteKeyNode.value;
                if ((tableBucket==deleteKeyNode)){
                    hashTable[keyHash]=tableBucket.next;
                }

                else tableBucket.next=node.next;

                return oldValue;
            }

        }

        return null;
    }

    /*
     * @param: []
     * @return: void
     * @author: Jerssy
     * @dateTime: 2021/3/26 12:14
     * @description: 遍历
     */
    public  void  printTable(){

        for (Node<K, V> kvNode : hashTable) {
            if (kvNode != null) {
                if (kvNode.next == null) System.out.println(kvNode.toString());

                 else {
                    Node<K, V> tempNode = kvNode;
                    List<String> list = new ArrayList<>();
                    while (tempNode != null) {
                         list.add(tempNode.toString());
                        tempNode = tempNode.next;
                    }
                    System.out.println(String.join("-->", list));
                }
            }
        }
    }

    /*
     * @param: []
     * @return: void
     * @author: Jerssy
     * @dateTime: 2021/3/26 14:29
     * @description: 简单扩容,正好再熟悉HashMap的底层扩容机制
     */
    private  Node<K, V>[]  resize(){
        int  newSize=defaultSize<<1;
        Node<K, V>[] newTable=new Node[newSize];
        Node<K, V> currentNode;int newHash = 0;
        Node<K, V>[]oldTable=hashTable;
        hashTable=null;
        for (Node<K, V> kvNode : oldTable) {
            if ((currentNode = kvNode) != null) {
                if (currentNode.next == null) {
                    newTable[newHash=currentNode.hash % newSize] = currentNode;
                } else {

                    Node<K, V> tempNode = currentNode;
                    Node<K, V> hNode = null, lNode = null;
                    while (tempNode!=null){
                        if ((currentNode.hash & defaultSize) == 0) {//低位链表
                            if (lNode == null) {
                                lNode = tempNode;
                            } else {
                                lNode.next = tempNode;
                            }
                        } else {//高位链表
                            if (hNode == null) {
                                hNode = tempNode;
                            } else {
                                hNode.next = tempNode;
                            }
                        }
                        tempNode = tempNode.next;
                    }
                    if (lNode!=null){
                        newTable[newHash]= lNode;
                    }
                    if (hNode!=null){
                        newTable[newHash+defaultSize]= hNode;
                    }
                }
            }
        }
        return newTable;
    }
}

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296