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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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<K,V>[] resize() { Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])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;
