[数据结构与算法]Java哈希表和哈希冲突

哈希表

Hash 一般翻译为散列，也有直接音为哈希的，这就是把任意长度的输入通过散列算法，变换

成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

哈希冲突

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，就把它叫做碰撞（哈希碰撞）。哈希碰撞的解决方案为开放地址法和链地址法。

以key/value的方式存储数据，采用拉链法综合了数组和链表结构。如果key已知则存取效率较高，但是删除慢，如果不知道key存取则慢，对存储空间使用不充分。最典型的实现是HashMap

JDK8+对桶内数据处理从链表转换为红黑树，则查询效率从O（N）提高到O(logN)。当链表中的个数超过8个时

会转换为红黑树

Map实现类

HashMap、TreeMap、LinkedHashMap、Hashtable等

HashMap

类定义

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable;

注意：Map接口的定义

public interface Map<K,V>没有父接口

具体的内部数据存储方式

transient Node<K,V>[] table;//哈希表的本质是一个数组，数组中每一个元素称为一个桶，桶中存放的是键值对

transient Set<Map.Entry<K,V>> entrySet; 并不是用于实际存储数据，主要用于针对entrySet和keySet两个视图提供支持。

transient int size;当前集合中的元素个数。

final float loadFactor ;当前集合的负载因子，当前Map集合中扩容的阈值【负载因子*最大容积】

transient int modCount；修改次数，主要用于实现多线程操作时快死异常

重要的阈值

• static final int DEFAULT_INITIAL_CAPACITY=1<<4;//aka16 默认的初始化容积

• static final int MAXIMUM_CAPACITY=1<<30;最大容积值，实际上就是2的30次方

• static final int TREEIFY_THRESHOLD = 8;//树化阈值：即链表转成红黑树的阈值，在存储数据时，当链表长

• 度 > 该值时，则将链表转换成红黑树

• static final int MIN_TREEIFY_CAPACITY = 64;//最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才

• 允许树形化链表 （即将链表转换成红黑树）否则，若桶内元素太多时，则直接扩容，而不是树形化

• static final int UNTREEIFY_THRESHOLD = 6;//桶的链表还原阈值：即红黑树转为链表的阈值，当在扩容resize

• ）时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红

• 黑树转换成链表

内部存储的实现

静态内部类用于实现Entry,HahMap中存放的key/value对就被封为Node对象。其中Key就是存放的键值，决定具体存放位置；

Value是具体存放数据，hash就是当前Node对象的hash值，next用于指向下一个Node

节点（单向链表）

HashMap()采用所有默认配置值，其中的参数值有initial Capacity：int初始化容积，默认值16，第二参数为加载因子，默认值为0.75，表示存储16*0.75个元素后，如果大于这个值则需要进行扩容。

Map主要用于存储键key值value对，根据键得到值，因此键不允许重复，但允许值重复。

HashMap是一个最常用的Map,它根据键的HashCode值存储数据，根据键可以直接获取它的值，

具有很快的访问速度。

HashMap最多只允许一条记录的键为null;允许多条记录的值为null

HashMap不支持线程的同步，即任一时刻可以有多个线程同时写Hash Map；可能会导致数据不一致，在JDK1.7中会出现环形链，虽然JDK1.8不会出现环形链，但是还会有rehash操作出现死循环、脏读问题、size值不准确等问题。如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力。

如何判断环形链？

创建一个Set,然后遍历整个集合，将每个元素的key值存入set,如果要存的key值已经存储在set中，则出现环型链.

Java7中使用Entry来代表每个HashMap中的数据节点，Java8中使用Node,基本没有区别，都是key,value,hash和next这四个属性，不过，Node只能用于链表的情况，红黑树的情况需要使用TreeNode。

TREEIFY_THRESHOLD为 8如果新插入的值是链表中的第 9 个会触发下面的 treeifyBin(树化操作，就是将单向链转换为红黑树)，也就是将链表转换为红黑树。

JDK8+插入数据到链表的最后面，Java7是插入到链表的最前面

HashMap的put方法的具体流程

public V put(K key, V value) { 以key存储value值，返回原始位置上的value值 先执行hash(key)根据key获取一个hash值, 参数2是要存储的key值，参数3是要存储的value，参数4表示如果当前位置已存在一个值 ，是否替换，false是替换，true是不替换。参数5是否在创建模式，如果为false，则表是在创建模式 return putVal(hash(key), key, value, false, true); }