Map集合原理的详解
一：Map是什么？
map是一个集合，一个键（key）和它对应的值构成map集合中的一个元素。Map中的元素是两个对象，一个对象作为键，一个对象作为值。键不可以重复，但是值可以重复。
二：HashMap
三：HashMap底层机制及源码分析
- HashMap底层维护了Node类型的数组table，默认为null；
- 当创建对象时，将加载因子（loadfactor）初始化为0.75；
- 当添加key-val时，第一次添加，则需要扩容table容量为16，临界值为12（16*0.75）
- 通过key的哈希值得到在table的索引，然后判断该索引处是否有元素，如果没有元素则直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否相等，如果相等，则直接替换val，如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时候发现容量不够，则需要扩容；
- 以后再扩容，则需要扩容table容量为原来的的2倍（32），临界值为原来的2倍，即24，以此类推；
- 在Java 8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）。
四：手写hashMap框架
public interface ExtMap<K, V> {
// 向集合中插入数据
public V put(K k, V v);
// 根据k 从Map集合中查询元素
public V get(K k);
// 获取集合元素个数
public int size();
// Entry的作用=== Node节点
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
}
public class ExtHashMap<K, V> implements ExtMap<K, V> {
// 1.定义table 存放HasMap 数组元素 默认是没有初始化容器 懒加载
Node<K, V>[] table = null;
// 2. 实际用到table 存储容量 大小
int size;
// 3.HashMap默认负载因子，负载因子越小，hash冲突机率越低， 根据每个链表的个数
float DEFAULT_LOAD_FACTOR = 0.75f;
// 4.table默认初始大小 16
static int DEFAULT_INITIAL_CAPACITY = 16; // 16
public V put(K key, V value) {
// 1.判断table 数组大小是否为空（如果为空的情况下 ，做初始化操作）
if (table == null) {
table = new Node[DEFAULT_INITIAL_CAPACITY];
}
// 2. hashMap 扩容机制 为什么要扩容？扩容数组之后，有什么影响？ hahsmap 中是从什么时候开始扩容
// 实际存储大小=负载因子*初始容量=DEFAULT_LOAD_FACTOR0.75*DEFAULT_INITIAL_CAPACITY16=12
// 如果size>12的时候就需要开始扩容数组,扩容数组大小之前两倍
if (size > (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)) {
// 需要开始对table进行属数组扩容
resize();
}
// 3.计算hash值指定下标位置
int index = getIndex(key, DEFAULT_INITIAL_CAPACITY);
Node<K, V> node = table[index];
if (node == null) {
// 没有发生hash冲突问题--- index冲突
node = new Node<K, V>(key, value, null);
size++;
} else {
Node<K, V> newNode = node;
while (newNode != null) {
// 已经发生hash冲突问题key 直接添加(冲突node)到前面了 不是往后面加
if (newNode.getKey().equals(key) || newNode.getKey() == key) {
// hashCodoe 相同，而且equals 相等情况 说明是同一个对象 修改值
// node.value = value;
return newNode.setValue(value);
} else {
// 继续添加，排在前面 hascode 取模余数相同 index 存放在链表 或者hashCode 相同但是对象不同
// 新的node 的next 原来的node
if (newNode.next == null) {
// 说明遍历到最后一个node ,添加node
node = new Node<K, V>(key, value, node);
size++;
}
}
newNode = newNode.next;
}
}
table[index] = node;
return null;
}
// 对table进行扩容
private void resize() {
// 1.生成新的table 是之前的两倍的大小 DEFAULT_INITIAL_CAPACITY*2
Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
// 2.重新计算index索引,存放在新的table里面
for (int i = 0; i < table.length; i++) {
// 存放在之前的table 原来的node
Node<K, V> oldNode = table[i];
// a 的index=1 b 的index=1
// a ##
while (oldNode != null) {
table[i] = null;// 赋值为null---为了垃圾回收机制能够回收 将之前的node删除
// 存放在之前的table 原来的node key
K oldK = oldNode.key;
// 重新计算index
int index = getIndex(oldK, newTable.length);
// 存放在之前的table 原来的node next
if (oldK.equals("22号") || oldK.equals("66号")) {
System.out.println("日志记录");
}
Node<K, V> oldNext = oldNode.next;
// 如果ndex 下标在新newTable发生相同的index时候,以链表进行存储 //
// 原来的node的下一个是最新的（原来的node存放下新的node下一个）
oldNode.next = newTable[index];
// 将之前的node赋值给 newTable[index]
newTable[index] = oldNode;
// 判断是否继续循环遍历
oldNode = oldNext;
}
}
// 3.将newtable赋值给老的table
table = newTable;
DEFAULT_INITIAL_CAPACITY = newTable.length;
newTable = null;/// 赋值为null---为了垃圾回收机制能够回收
}
public static void main(String[] args) {
new ExtHashMap<String, String>().test();
}
private String age;
public void test() {
// ExtHashMap map1 = new ExtHashMap<K, V>();
// map1.age = "10";
// ExtHashMap map2 = map1;
// map.age = "20";
// System.out.println(map1.age + "," + map2.age);
// Node[] newTables = new Node[DEFAULT_INITIAL_CAPACITY << 1];
// Node<String, String> node = new Node<String, String>("001", "001",
// null);
// newTables[0] = node;
// Node<String, String> newNode = new Node<String, String>("002", "001",
// null);
// node = newNode;
// System.out.println(newTables[0] == node);
}
// 测试方法.打印所有的链表元素
void print() {
for (int i = 0; i < table.length; i++) {
Node<K, V> node = table[i];
System.out.print("下标位置[" + i + "]");
while (node != null) {
System.out.print("[ key:" + node.getKey() + ",value:" + node.getValue() + "]");
node = node.next;
// if (node.next != null) {
// node = node.next;
// } else {
// // 结束循环
// node = null;
// }
}
System.out.println();
}
}
public int getIndex(K k, int length) {
int hashCode = k.hashCode();
// System.out.println("k:" + k + ",hashCode=" + hashCode);
int index = hashCode % length;
return index;
}
public V get(K k) {
Node<K, V> node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);
return node == null ? null : node.value;
}
public Node<K, V> getNode(Node<K, V> node, K k) {
while (node != null) {
if (node.getKey().equals(k)) {
return node;
}
node = node.next;
}
return null;
}
public int size() {
return size;
}
// 定义节点
class Node<K, V> implements Entry<K, V> {
// 存放Map 集合 key
private K key;
// 存放Map 集合 value
private V value;
// 下一个节点Node
private Node<K, V> next;
public Node(K key, V value, Node<K, V> next) {
super();
this.key = key;
this.value = value;
this.next = next;
}
public K getKey() {
return this.key;
}
public V getValue() {
return this.value;
}
public V setValue(V value) {
// 设置新值的返回老的 值
V oldValue = this.value;
this.value = value;
return oldValue;
}
}
}
五：HashMap 的长度为什么是2的幂次方
- 为了优化取模性能和降低哈希碰撞概率
（1）首先是运算效率，我们都知道计算机是以二进制存储的。与运算符(&)是计算机中的一个基本的逻辑运算方式，它的运算方式是只能两者都为1的时候才等于1，否则等于0。但是想用&与运算符进行计算的前提必须是为2的幂次方
（2）长度是2的幂次方，Length - 1的值的二进制所有的位均为1，这种情况下，Index的结果等于hashCode的最后几位。只要key的hashCode本身符合均匀分布，Hash算法的结果就是均匀的
六：jdk 1.7 并发扩容死链问题
原因：hashmap在扩容到2倍新容器时，由于采用的是头插法「头插法就是总是把新增结点插在头部」，会造成链表翻转形成闭环，也就是形成死循环
死循环执行步骤1
死循环是因为并发HashMap扩容导致的，并发扩容的第一步，线程T1和线程T2要对HashMap进行扩容操作，此时T1和T2指向的是链表的头结点元素A，而T1和T2的下一个节点，也就是T1.next和T2.next指向的是B节点，如下图所示： 
死循环执行步骤2
死循环的第二步操作是，线程T2时间片用完进入休眠状态，而线程T1开始执行扩容操作，一直到线程T1扩容完成后，线程T2才被唤醒，扩容之后的场景如下图所示：
从上图可知线程T1执行之后，因为是头插法，所以HashMap的顺序已经发生了改变，但线程T2对于发生的一切是不可知的，所以它的指向元素依然没变，如上图展示的那样，T2指向的是A元素，T2.next指向的节点是B元素。
死循环执行步骤3
当线程T1执行完，而线程T2恢复执行时，死循环就建立了，如下图所示：
因为T1执行完扩容之后B节点的下一个节点是A，而T2线程指向的首节点是A，第二个节点是B，这个顺序刚好和T1扩完容完之后的节点顺序是相反的。T1执行完之后的顺序是B到A，而T2的顺序是A到B，这样A节点和B节点就形成死循环了，这就是HashMap
七：HashTable和HashMap区别？
- HashMap不是线程安全
- HashTable不允许key和value为null；是线程安全的