一：概述
散列表的读写操作：
通过哈希函数，就可以在散列表中进行读写操作了。
二：具体说明
写操作
操作就是散列表中插入新的键值对(JDK中叫作Entry)。
* 如调用hashMap.put(“002931″,”王五”)，意思是插入一组Key为002931、Value为王五的键值对。
* 具体步骤：
* 第1步：通过哈希函数，把Key转化成数组下标5.
* 第2步：如果数组下标5对应的位置没有元素，就把这个Entry(键值对)填充到数组下标5的位置
0 1 2 3 4 5 6 7
null null null null null Entry null null
但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的key通过
* 哈希函数获得的下标可能是相同的。例如002936这个key对应的数组下标为2，002947这个Key
* 对应的数组下标也为2
* 像这种情况，就叫做哈希冲突(如下图所示)
开放寻址法的原理很简单，当一个key通过哈希函数获得对应的数组下标已被占用时
* 我们可以“另谋高就”，寻找下一个空闲的位置
*
* 以上面情况为例，Entry通过哈希函数得到下标2，垓下标在数组中已经有了其他元素，那么就向后移动1位
* 看看数组下标3的位置是否有空。
* 但是，下标3也被占用了，那么就再向后移动一位，看看数组下标4的位置是否有空。
如下图所示：
很不巧，下标3已经被占用，那么就再向后移动一位，看看数组下标为4的位置。
幸运的是，数组下标4的位置还没有被占用，因此就把entry6放入数组下标为4的位置。
这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方式有很多种，并一定只是简单地寻找
* 当前元素的最后一个元素，这里是一个简单的示例。
JAVA中，ThreadLocal使用的就是开放寻址法。
- * 接下来，重点讲一下解决哈希冲突的另一种方法-链表法。这种方法被应用于在
- * Java的集合类HashMap中。
- * HashMap数组中的每一个元素不仅是一个Entry对象那，还是一个链表的头节点。每一个Entry对象通过
- * next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位时，只需要插入对应的链表中即可
读操作(get)
* 讲完了写操作，再来讲一下读操作。读操作就是通过给定的key(键)，在散列表中查找对应的Value。
* 例如调用hashMap.get(“002936”),意思是查找key为002936的Entry在散列表中所对应的值
* 具体步骤：
* 第1步：通过哈希函数，把key转换成数组下标2.
* 第2步：找到数组下标2所对应的元素，如果这个元素的key为002936，那么就找到了，如果这个Key
* 不是002936也没关系，由于数组的每一个元素都与一个链表对应，我峨嵋你可以顺着链表慢慢往下找，看看
* 是否可以找到与Key相匹配的节点。
简单来说就是一个键对应一个相应的value值。
再上图中，首先查找节点Entry6的key是002947，和待查找的Key 002936不符。接着定位到链表的下一个节点Entry1，发现Entry1的key就是我们需要找的,所以返回Entry1的Value即可。
扩容
在之前博客文章数据结构之数组内容中提及到数组扩容。
* 因为散列表是基于数组实现的，那么散列表也要涉及到扩容问题
* 扩容不是从始至终都需要做的，它有一个时刻(即遇到要扩容的情况时)。
* 当经过多次元素插入，散列表达到一定的饱和度时，Key映射位置发生冲突会逐渐的提高。
* 经过这样的叠加，最终会使大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续的
* 插入和查询操作的效率(性能)有很大的影响。
这时，散列表就需要扩展它的长度，也就是进行扩容。
对于服务器托管网JDK中的散列表实现类HashMap来说，影响其扩容的因素有两个。
Capacity,即HashMap的当前长度。
LoadFactor,即HashMap的负载因子，默认值为0.75f
衡量HashMap需要进行扩容的条件为：
HashMap.Size >= Capacity * LoadFactor
散列表的扩容操作并不是简单的把散列表的长度扩大，而是经历了下面两个过程：
- 扩容，创建一个新的Entry空数组，长度是为原数组的2倍。
- 重新Hash,遍历原Entry数组，把所有的Entry重新Hash到新数组中。
重新Hash的原因是：长度扩大以后,Hash的规则也随之改变。
经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。
扩容前的HashMap
扩容后的HashMap
以上就是散列表的各种基本操作原理。由于HashMap的实现代码相比较比较复杂，由于能力限制，源码就步赘述了。如果感兴趣的话可以在JDK中直接阅读HashMap类的源码。
值得注意的是：关于HashMap的实现，JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。如果想深入了解可以认真的去看看。
三：数据结构基础总结(即数组，链表，栈，队列，散列表)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: CSDN问答机器人
前言
一、背景
二、总体流程
三、构建知识库
四、粗排
五、精排
六、Prompt
总结
相关博客文章目录 前言 一、背景 二、总体流程 三、构建知识库 四、粗排 五、精排 六、Prompt 总结 相关博客 前言 先看结果: 已经连续很多周获得了第二名(万年老二), 上周终于拿了一回第一, 希望继续保持. 😁 这是今天的榜单, 采纳的数量相对较少, 之前基…
