1.哈希表结构的优势？
哈希表作为一种优秀数据结构
本质上存储结构是一个数组，辅以链表和红黑树
数组结构在查询和插入删除复杂度方面分别为O(1)和O(n)
链表结构在查询和插入删除复杂度方面分别为O(n)和O(1)
二叉树做了平衡 两者都为O(lgn)
而哈希表两者都为O(1)
2.哈希表简介
哈希表本质是一种(key,value)结构
由此我们可以联想到，能不能把哈希表的key映射成数组的索引index呢？
如果这样做的话那么查询相当于直接查询索引，查询时间复杂度为O(1)
其实这也正是当key为int型时的做法 将key通过某种做法映射成index，从而转换成数组结构
3.数据结构实现步骤
1.使用hash算法计算key值对应的hash值h(默认用key对应的hashcode进行计算(hashcode默认为key在内存中的地址)),得到hash值
2.计算该(k,v)对应的索引值index
索引值的计算公式为 index = (h % length) length为数组长度
3.储存对应的(k,v)到数组中去，从而形成a[index] = node<k,v>,如果a[index]已经有了结点
即可能发生碰撞，那么需要通过开放寻址法或拉链法(Java默认实现）解决冲突
当然这只是一个简单的步骤，只实现了数组 实际实现会更复杂
hash表 数组类似下图
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| --- | null | null | <10,node1> | <27,node2> | null | null | null | null |
| --- |
两个重要概念
哈希算法
h 通过hash算法计算得到的的一个整型数值
h可以近似看做一个由key的hashcode生成的随机数，区别在于相同的hashcode生成的h必然相同
而不同的hashcode也可能生成相同h，这种情况叫做hash碰撞，好的hash算法应尽量避免hash碰撞
(ps:hash碰撞只能尽量避免，而无法杜绝,由于h是一个固定长度整型数据,原则上只要有足够多的输入，就一定会产生碰撞)
关于hash算法有很多种，这里不展开赘述，只需要记住h是一个由hashcode产生的伪随机数即可
同时需要满足key.hashcode -> h 分布尽量均匀(下文会解释为何需要分布均匀)
可以参考https://blog.csdn.net/tanggao1314/article/details/51457585
解决碰撞冲突
由上我们可以知道，不同的hashcode可能导致相应的h即发生碰撞
那么我们需要把相应的<k,v>放到hashmap的其他存储地址
解决方法1：开放寻址法
通过在数组以某种方式寻找数组中空余的结点放置
基本思想是：当关键字key的哈希地址p=H（key）出现冲突时
以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，
解决方法1：链地址法
通过引入链表 数组中每一个实体存储为链表结构，如果发生碰撞，则把旧结点指针指向新链表结点，此时查询碰撞结点只需要遍历该链表即可
在这种方法下，数据结构如下所示
int类型数据 hashcode 为自身值
链地址法示例图
在JAVA中几个细节点
1.为什么需要扩容？扩容因子大还是小好？
由于数组是定长的，当数组储存过多的结点时，发生碰撞的概率大大增加，此时hash表退化成链表
过大的扩容因子会导致碰撞概率大大提升，过小扩容因子会造成存储浪费，在Java中默认为0.75
2.当从哈希表中查询数据时，如果key对应一条链表,遍历时如何判断是否应该覆盖？
当遍历链表时，如果两个key.hashcode的h一致会调用equals()方法判断是否为同一对象,equal的默认实现是比较两者的内存地址
因此为什么Java强调当重写equals()时需要同时重写hashcode()方法,假设两个不同对象，在内存中的地址不同分别为a和b,那么重写equals()以后a.equals(b) =true 开发者希望把a,b这两个key视作完全相等
然而由于内存地址的不同导致hashcode不同,会导致在hashmap中储存2个本应相同的key值
这里提供一个范例
public class Student {
//学号
public int student_no;
//姓名
public String name;
@Override
public boolean equals(Object o) {
Student student = (Student) o;
return student_no == student.student_no;
}
}
通常情况下我们像上图一样期望通过判断两个Student的学号是否是否为同一学生
然而在使用map或set集合时产生出乎意料的结果
image.png
当我们重写hashcode()时
@Override
public int hashCode() {
return Objects.hash(student_no);
}
可以看到现在可以正常使用集合框架中的一些特性
image.png
3.为什么在HashMap中数组的长度length = 2^n（初始值为16） ?
当计算索引值index = h % length 由于计算机的取余操作速度很慢，而计算机的按位取余 & 的操作非常快,又因为 h%length = h & (length-1) (需要满足length = 2^n) 因此规定了length = 2^n 加快index的计算速度 上式的证明参考http://yananay.iteye.com/blog/910460
4.HashMap的红黑树在哪里体现呢？
红黑树是JDK8中对hashmap作的一个变更，在JDK7之前，HashMap采用数组+链表的形式存储数据，我们知道优秀的hash算法应避免碰撞的发生,但假如开发者使用了不合适的hash算法，O(1)级别的数组查询会退化到O(n)级链表查询，因此在JDK8中引入红黑树的，当一个结点的链表长度大于8时，链表会转换成红黑树，提高查询效率,而链表长度小于6时又会退化成链表
5.扩容是如何触发的?
当hashmap中的size > loadFactory * capacity即会发生扩容，size 也是数组结点和链表结点的总和,要明确扩容是一个非常耗费性能的操作，因为数组的长度发生改变，需要对所有结点的索引值重新进行计算,而在JDK8中对这部分进行了优化，详细可以参考https://blog.csdn.net/aichuanwendang/article/details/53317351,在扩容完后减轻了碰撞产生的影响
在正常的Hash算法下，红黑树结构基本不可能被构造出来，根据概率论，理想状态下哈希表的每个箱子中，元素的数量遵守泊松分布:
P(X=k) = (λ^k/k!)e^-λ,k=0,1,...
当负载因子为 0.75 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下:(参考https://blog.csdn.net/Philm_iOS/article/details/81200601)，下述分布来自源码文档
> * Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
JDK的设计者为了开发者真是煞费苦心= =
网友评论