Map Map关系图 对象名称 具体实现 线程是否安全 是否有序 是否允许空 Hashtable 基于数组、Entry实体 安全 否 否 HashMap Comparator、Entry实体 不安全 有 否 HashMap基本原理 基本结构:水平轴为数组,垂直轴为链表 HashMap的初始容量为16,默认的负载因子为0.75;当数据量大于容量*负载因子时,此时则扩容; HashMap如何扩容?通过位运算左移1位 HashMap如何解决Hash冲突?通过拉链法解决Hash冲突 HashMap何时进行链表结构变换?当链表长度数目大于8且Table长度大于64时 HashMap如何解决线程不安全？ 使用HashTable 使用ConcurrentHashMap 使用Collections.synchronizedMap TreeMap基础 不允许出现重复的Key 不允许key、Value为空 可排序 HashTable基础 不允许key、Value为空 线程安全 LinkedHashMap基础 基于HashMap,维护了一个链表 HashMap源码分析 HashMap流程图: HashMap关键方法 • tableSizeFor(initialCapacity):容量初始化;通过|,>>>运算保证容量始终为二的幂次;纠正用户输入的上限值为2的幂次 /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } • putVal()方法:插入数据 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //判断table是否为空 if ((tab = table) == null || (n = tab.length) == 0) //初始化table大小 n = (tab = resize()).length; //tab[i]是否存在元素 if ((p = tab[i = (n - 1) & hash]) == null) //tab[i]如果不存在,则直接插入 tab[i] = newNode(hash, key, value, null); else { Node e; K k; //记录节点p if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果p节点是树节点 else if (p instanceof TreeNode) //则直接插入 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //遍历p链表 for (int binCount = 0; ; ++binCount) { //如果p的下一个节点为null if ((e = p.next) == null) { //则直接追加 p.next = newNode(hash, key, value, null); //当连边数目大于8时,触发树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果节点存在,则解决Hash冲突 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //修改标志位modCount,fail-fast机制;保证并发的安全性 ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } • resize()方法:初始化、扩容 final Node[] resize() { Node[] oldTab = table; //获取tab的大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //如果tab.length大于0 if (oldCap > 0) { //如果tab大于MAX_INTEGER,则直接返回 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //如果容量扩大两倍后,依然小于MAXIMUM_CAPACITY;且tab.length大于64 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //阈值也扩容为原来的两倍 newThr = oldThr << 1; // double threshold } //当通过initialCapacity构造方法构造map时,初始化时定义了oldThr else if (oldThr > 0) // initial capacity was placed in threshold //将oldThr赋予newCap newCap = oldThr; //默认无参构造方法 else { //初始化容量为16;阈值为12 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新的阈值为0 if (newThr == 0) { float ft = (float)newCap * loadFactor; //修正新的阈值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //扩容之后的元素复制操作 @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; //接下来属于扩容完成后的元素复制操作....... } • hash(Object key):HashMap的hash策略,将高位地址转换为低位地址,防止高位、地位地址分布不均;解决易发生Hash冲突 static final int hash(Object key) { int h; //通过key的hashcode与key的hashcode无符号右移16位作异或运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } HashMap允许key为null;