Hash表

Hash表

• Hash表的结构就是顺序表+链表的结构
  Hash表(jdk1.7)中内部是HashMapEntry<K,V>[] table 是一个HashMapEntry的数组，
  就是这个HashMapEntry既具备了顺序表的修改查找快的特点，也具备了链表增加删除快的特点。

HashMapEntry内部类中包含 key value hash next 等成员变量，就是通过这些来实现了顺序表+链表的结构

HashMap

• 上图中一个黄色的块代表一个数组，蓝色的连接起来代表一个个列表

Hash如何保存数据的

如下图：

Hash表

HashMap中的key有什么用？

• 通过key计算hash值，并且通过算法，转变为数组的index，这样就可以实现快速定位，从而快速查找

int index = hash & (tab.length-1);

HashMap添加数据的原理

添加数据时，创建了一个新的HashMapEntry对象

table[index] = new HashMapEntry<k,v>(key,v,hash,index)

然后将创建的新的节点存入到table数组的对应Index的位置
如果发现对应Index中已经有了节点，那么再次存储index位置时

image.png

当hash运算冲突时，会进行判断，已经存储的值和要存储的值是不是同一个，如果是同一个，就进行覆盖。如果不是同一个

Hash性能优化

• 由于超过HashMap的默认大小阈值后会进行扩容，而扩容会频繁遍历数组和链表，所以我们要避免频繁进行扩容，所以我们在创建HashMap的时候要预估一个大小，尽量使得创建的HashMap长度够用

HashMap hmap = new HashMap(默认大小);