哈希表和有序表的简单介绍哈希表的简单介绍

哈希表的简单介绍

• 哈希表是一种集合结构 包含map和set
• 如果只有key，没有伴随数据value，可以使用HashSet结构(C++  stl set)
• 如果拥有key，拥有伴随数据value，可以使用HashMap结构(C++ stl map)
• 有无伴随数据是Hashmap和Hashset的唯一区别，底层的实际结构都是一回事，都是使用的红黑树

哈希冲突的解决办法

1，开放寻址法：如果指定位置上存在元素，那么就在存储在指定位置的下一个元素，如果仍然被占用，继续移动。以此类推，直到找到一个合适的位置。寻址的方式有很多，这仅仅是一个简单的例子。Java里面的ThreadLocal就是开放寻址法

2，链表法：Java里面的HashMap，每一个元素不仅是是一个Entry对象，还是一个链表的头部节点。每一个Entry对象通过指针指向他的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入对应的链表中即可

散列表扩容

1，多次元素的插入，单列表达到一定的饱和度时候，key映射位置时发生的冲突的概率会逐渐提高；这样大量的元素会拥挤在相同的数组的下标的位置，会形成很长的链表，对后续的插入和查询操作的性能有很大的影响

对于JDK中的HashMap而言，影响扩容的因素有两个：1，capacity：即当前的长度；2，loadfactor：负载因子，默认数值为0.75f

衡量HashMap需要扩容的条件是：HashMap.size >= Capacity * LoadFactor

扩容操作 具体干了什么事清呢？

1，扩容，创建一个新的Entry空的数组，长度是先前的2倍

2，重新Hash，遍历先前的Entry数组，将所有的元素重新进行Hash到新的数组中，这是因为长度扩大之后，Hash的规则也会随之改变，将先前的Entry重新得到了尽可能均匀的分配

* 当多个Entry被Hash到同一个数组下标的位置时，为了提升插入和查找的效率，HashMap会把Entry链表转化为红黑树的结构

最后

以上就是过时火车为你收集整理的哈希表和有序表的简单介绍哈希表的简单介绍的全部内容，希望文章能够帮你解决哈希表和有序表的简单介绍哈希表的简单介绍所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。