散列表也叫做哈希表(hash table),这种数据结构提供了键(key)和值(value)的映射关系。只要给出一个key，就可以高效查找它匹配的value，时间复杂度接近O(1);
哈希函数通过某种方式，把key和数组下标进行转换。 在java中，每个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，他们的hashcode都是一个整型变量。 最简单的转化方式是按照数组长度进行取模运算：
index = HashCode(Key)%Array.lengthJDK中的哈希函数并没有直接采取取模运算，而是利用位运算的方式来优化性能。 通过哈希函数，我们可以把字符串或其他类型的Key，转化成数组的下标index 例如长度为8的数组
key = 001121, index = HashCode(“001121”)%Array.length=1420036703%8=7
1、写操作：在散列表中插入新的键值对 例如调用：
hashMap.put("002931","王五");具体实现方式： 1、通过哈希函数，将key转换成数组下标，例如5 2、如果数组小标5对应的位置没有元素，就把这个键值对填充到数组下标为5的位置 但是，由于数组的长度是有限的，当插入的键值对越来越多，不同的key通过哈希函数获得的下标可能是相同的 这种情况叫做哈希冲突 例如：
002936的对应数组下标为2,； 002947的对应数组下标也是2；
哈希冲突是无法避免的。解决哈希冲突的方法： 1、开放寻址法 例如：第6组键值对通过哈希函数得到下标2，该下标在数组中已经有了其他元素，那么就向后移动1位，观察数组下标3是否有空 如果下标3也被占用，那么就再向后移动，直到找到空的位置。 （寻址的方式有很多，并不一定只是简单地寻找当前元素的后一个元素，这里只是简单举例） 2、链表法 HashMap数组的每个元素不仅是一个键值对对象，还是一个链表的头结点。每一个键值对对象通过next指针指向它的下一个键值对结点。当新来的键值对映射到与之冲突的数组位置时，只需要插入对应的链表中即可： 如下图： 2、读操作：通过给定的key，在散列表中查找对应的value 例如：调用函数hashMap.get(“002936”) 具体步骤：（以链表法为例） 1、通过哈希函数，将key转换成数组下标，例如2 2、找到数组下标2对应的元素，如果这个元素的key是002936，那么就找到了 如果这个key不是002936，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与key相匹配的结点
3、扩容操作： 当经过多次元素插入，散列表达到一定的饱和度时，key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置形成很长的链表，对后续的插入和查询操作都会有很大影响。 此时就需要进行扩容： 影响扩容的因素： 1、HashMap当前长度 2、HashMap的负载因子，默认值为0.75f(在JDK中) 衡量HashMap需要进行扩容的操作如下：
HashMap.Size>=Capacity x LoadFactor扩容具体步骤： 1、扩容，创建一个新的键值对空数组，长度是原数组的两倍 2、重新Hash，遍历原来的键值对数组，把所有的键值对重新Hash到新数组中（因为数组长度变化后，hash的规则也发生变化了） 经过扩容后，散列表重新变得稀疏。
