HashMap详解

一键三连是对我的最大动力哦铁子们！！！！！！！！！！！

1.集合的类型

1.list 有序，可重复

1. ArrayList数组列表，有序，可重复，内部是通过Array实现。对数据列表进行插入、删除操作时都需要对数组进行拷贝并重排序。因此在知道存储数据量时，尽量初始化初始容量，提升性能。

2. LinkedList双向链表，每个元素都有指向前后元素的指针。顺序读取的效率较高，随机读取的效率较低。

3. Vector向量，线程安全的列表，与ArrayList一样也是通过数组实现的，不同的是Vector是线程安全的，也即同一时间下只能有一个线程访问Vector，线程安全的同时带来了性能的耗损，所以一般都使用ArrayList。

4. Stack栈，后进先出（LIFO），继承自Vector，也是数组，线程安全的栈。但作为栈数据类型，不建议使用Vector中与栈无关的方法，尽量只用Stack中的定义的栈相关方法，这样不会破坏栈数据类型。

5. ArrayQueue数组队列，先进先出（FIFO）

2.Queue队列，有序、可重复

1. ArrayDeque数组实现的双端队列，可以在队列两端插入和删除元素

2. LinkedList也是双向链表

3. PriorityQueue优先队列，数组实现的二叉树，完全二叉树实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

3.Map映射 /字典，无序，键值对，键唯一

1. HashMap哈希映射/字典，无序字典，键值对数据，key是唯一的，Key和Value都可以为null

2. TreeMap红黑树实现的key->value融合，可排序，红黑树是一种自平衡二叉查找树。

3. LinkedHashMap链表映射/字典，继承了hashmap的所有特性，同时又实现了双向链表的特性，保留了元素插入顺序。

2.HashMap和HashSet和HashTable的区别

2.1HashSet和HashMap的区别

相同点：1.都是采用的Hash散列算法分配的数据，2.都是线程不安全的，3.数据查询是无序的

不同点：1.继承的父类不同 2.set的单键，而hashmap是可以存键值对 3.hashmap是可以存不同的value但是hashset不支持相同value数据

2.2HashTable和HashMap的区别

相同点：1.都是采用的Hash散列算法分配的数据，2.都是采用的键值对的方式存储数据， 3.底层都是用的键值对加链表的形式，4.都是继承了map接口

不同点：

1.HashTable叠加了syconize关键字是线程安全的，HashMap是线程不安全的

2.HashTable是不允许键或者值为null的，HashMap可以

3.HashTable的hash算法是直接根据原始hashCode计算的，HashMap就是根据自定义的Hash算法

4.HashTable的底层扩容机制是当前容量翻倍+1，HashMap的底层扩容机制是当前容量翻倍

5.HashTable的初始化容量不同，HashTable的初始化容量为11，HashMap的初始化容量为16

3.HashMap的原始参数

/**
 * The default initial capacity - MUST be a power of two.
    默认初始容量--必须是2的倍数
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
​
/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
    //最大初始容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
​
/**
 * The load factor used when none specified in constructor.
    加载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
​
/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
    链表转换树的大小值
 */
static final int TREEIFY_THRESHOLD = 8;
​
/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
    树转换链表的大小值
 */
static final int UNTREEIFY_THRESHOLD = 6;
​
/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
    将容器树形化的最小表容量
 */
static final int MIN_TREEIFY_CAPACITY = 64;

4.HashMap的putVal方法

1.根据判定当前map的大小，如果为null或者length为0则初始化map

2.根据hash和key值判定当前存的entry的key是否存在当前相同的key如果存在，则替换value

3.如果不存在则加一个node块，将entry放进新的node块中

4.根据hash去判断当前hash是否已存在数组中，如果存在，则新建链表，将老数据的值通过afterNodeAccess放在了链表里，新数据置于表头

5.如果链表数量达到8并且，当前map的大小已经到达64的时候，当前链表则会升级为红黑树

6.通过每次调用的时候，进行检测红黑树在回退阈值（6）的时候就会自动回退成链表

7.插入完成以后，map的大小加一同时检测map的大小是否已经到达当前数组的扩容阈值数量，如果到达就resize（）扩容

5.HashMap的getNode方法

1.通过传hash和key的参数来判定的数据

2.如果当前hash相同但是key不同，就是会去当前node块中链表式搜索对应的key

3.最终取到当前key和hash均相同的数据

6.ConcurrentHashMap

1.7的版本

Java7 中 ConcruuentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

1.8的版本

Java8 中的 ConcruuentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表