数据结构-哈希表

介绍像线性数据结构在查找的时候⼀般都是使⽤ 或者! 在折半查找或者其他范围查询的时候可能会使⽤ 和 ,理想的时候我们肯定希望不经过任何的⽐较直接能定位到某个位置存储位置这种在数组中可以通过索引取得元素。那么如果我们将需要存储的数据和数组的索引对应起来并且是⼀对⼀的关系那不就可以很快定位到元素的位置了么只要通过函数f(k) 就能找到k 对应的位置这个函数f(k) 就是hash 函数。它表示的是⼀种映射关系但是对不同的值可能会映射到同⼀个值同⼀个hash 地址也就是f(k1) f(k2) 这种现象我们称之为冲突或者碰撞。hash 表定义如下散列表Hash table也叫哈希表是根据键Key⽽直接访问在内存储存位置的数据结构。也就是说它通过计算⼀个关于键值的函数将所需查询的数据映射到表中⼀个位置来访问记录这加快了查找速度。这个映射函数称做散列函数存放记录的数组称做散列表。⼀般常⽤的hash 函数有直接定址法取出关键字或者关键字的某个线性函数的值为哈希函数⽐如H(key) key 或者H(key) a * key b数字分析法对于可能出现的数值全部了解取关键字的若⼲数位组成哈希地址平⽅取中法取关键字平⽅后的中间⼏位作为哈希地址折叠法将关键字分割成为位数相同的⼏部分最后⼀部分的位数可以不同取这⼏部分的叠加和舍去进位作为哈希地址。除留余数法取关键字被某个不⼤于散列表表⻓m 的数p 除后所得的余数为散列地址。即h ash(k)k mod p p m 。不仅可以对关键字直接取模也可在折叠法、平⽅取中法等运算之后取模。对p 的选择很重要⼀般取素数或m 若p 选择不好容易产⽣冲突。随机数法取关键字的随机函数值作为它的哈希地址。但是这些⽅法都⽆法避免哈希冲突只能有意识的减少。那处理hash 冲突⼀般有哪些⽅法呢解决哈希冲突的三种方法拉链法、开放地址法、再散列法拉链法HashMapHashSet其实都是采用的拉链法来解决哈希冲突的就是在每个位桶实现的时候采用链表的数据结构来去存取发生哈希冲突的输入域的关键字也就是被哈希函数映射到同一个位桶上的关键字但是如果hash 冲突⽐较严重链表会⽐较⻓查询的时候需要遍历后⾯的链表因此JDK 优化了⼀版链表的⻓度超过阈值的时候会变成红⿊树红⿊树有⼀定的规则去平衡⼦树避免退化成为链表影响查询效率。但是你肯定会想到如果数组太⼩了放了⽐较多数据了怎么办再放冲突的概率会越来越⾼其实这个时候会触发⼀个扩容机制将数组扩容成为 2 倍⼤⼩重新hash 以前的数据哈希到不同的数组中。hash 表的优点是查找速度快但是如果不断触发重新 hash , 响应速度也会变慢。同时如果希望范围查询 hash 表不是好的选择。拉链法的装载因子为n/mn为输入域的关键字个数m为位桶的数目开放地址法所谓开放地址法就是发生冲突时在散列表也就是数组里里去寻找合适的位置存取对应的元素就是所有输入的元素全部存放在哈希表里。也就是说位桶的实现是不需要任何的链表来实现的换句话说也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候先通过哈希函数进行判断若是发生哈希冲突就以当前地址为基准根据再寻址的方法探查序列去寻找下一个地址若发生冲突再去寻找直至找到一个为空的地址为止。探查序列的方法:线性探查平方探测伪随机探测线性探查di 123…m-1这种方法的特点是冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表。使用例子ThreadLocal里面的ThreadLocalMap中的set方法javaprivate void set(ThreadLocal? key, Object value) { // We dont use a fast path as with get() because it is at // least as common to use set() to create new entries as // it is to replace existing ones, in which case, a fast // path would fail more often than not. Entry[] tab table; int len tab.length; int i key.threadLocalHashCode (len-1); //线性探测的关键代码 for (Entry e tab[i]; e ! null; e tab[i nextIndex(i, len)]) { ThreadLocal? k e.get(); if (k key) { e.value value; return; } if (k null) { replaceStaleEntry(key, value, i); return; } } tab[i] new Entry(key, value); int sz size; if (!cleanSomeSlots(i, sz) sz threshold) rehash(); }但是这样会有一个问题就是随着键值对的增多会在哈希表里形成连续的键值对。当插入元素时任意一个落入这个区间的元素都要一直探测到区间末尾并且最终将自己加入到这个区间内。这样就会导致落在区间内的关键字Key要进行多次探测才能找到合适的位置并且还会继续增大这个连续区间使探测时间变得更长这样的现象被称为“一次聚集primary clustering”。平方探测在探测时不一个挨着一个地向后探测可以跳跃着探测这样就避免了一次聚集。di12-1222-22…k2-k2这种方法的特点是冲突发生时在表的左右进行跳跃式探测比较灵活。虽然平方探测法解决了线性探测法的一次聚集但是它也有一个小问题就是关键字key散列到同一位置后探测时的路径是一样的。这样对于许多落在同一位置的关键字而言越是后面插入的元素探测的时间就越长。这种现象被称作“二次聚集(secondary clustering)”,其实这个在线性探测法里也有。伪随机探测di伪随机数序列具体实现时应建立一个伪随机数发生器如i(ip) % m生成一个位随机序列并给定一个随机数做起点每次去加上这个伪随机数就可以了。