本篇源码来自JDK1.8.
Java的位运算和取模取余操作说明:
位运算(&)效率要比取余运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
X % 2^n = X & (2^n - 1)
2^n表示2的n次方,也就是说,一个数对2^n取余 == 一个数和(2^n - 1)做按位与运算 。
假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 -1 = 7 ,即0111。
此时X & (2^3 - 1) 就相当于取X的2进制的最后三位数。
右移和取模
从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。
HashMap的初始化:
可以是无参数的初始化,也可以指定初始大小和加载因子。
第一次添加元素时,进行第一次扩容,设置一个大小为16的数组,其中包含的元素为Node<K,V>,扩容的临界值为0.75 * 16 = 12,即等到大小超过12时再次进行扩容。
Node<K,V>结点包含4个元素:
Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next;//next用于处理有冲突的情况, }
扩容时,会把旧的数组中的元素,重新计算索引,放入新的数组中。
newTab[e.hash & (newCap - 1)] = e;//根据元素的hash值与当前的容量-1,进行位元素,相当于取余操作
扩容时,新的size计算,新的容量=旧的容量*2:
if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold }
HashMap初始化时,如果指定了一个集合,或者指定了一个初始大小,则会自动计算出一个比它大的最近的2^n值作为初始化数组的大小。计算数组大小的方法如下:
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; }
HashMap的put方法:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);//通过key,获取一个hash值 }
获取hash值的算法,用key的hashcode值高16位于低16位进行异或操作。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
HashMap中解决冲突的方法, 先用线性链表来保存冲突,如果冲突链表长度超过8,则使用红黑树结构。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)//put时,没有冲突,直接新建一个Node。 tab[i] = newNode(hash, key, value, null); else { //如果此处有Node,则解决冲突 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
put方法(新增元素)总结:
计算元素数组下标的方法:通过元素Key的hash值与数组容量取余。
hash值相同,则产生冲突。但是hash值相同,不一定key相同。
1,通过key值获取一个hash值。
2,判断当前是否达到临界值,确定是否扩容,扩容则会把当前的容量扩大一倍。扩容时,会重新根据元素的hash值和新的数组容量,计算元素的数组下标。
3,新建一个Node结点,计算数组下标,放入对应的位置,如果有冲突,则添加进链表或者红黑树。产生冲突时,如果新增的Node结点的key与之前的key相同,则返回之前的key对应的value值。
根据Key值获取对象:
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//判断hash和equals,都相等,则获取成功; return first; if ((e = first.next) != null) {//否则从链表中往下寻找。 if (first instanceof TreeNode) //如果是红黑树,则从红黑树中获取Node. return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { // 否则从线性链表中搜索. if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
由于HashMap的扩容需要重新计算各个已有元素的hash值,并重新调整数组下标,是一个耗时的操作,因此最好初始化时就指定HashMap的容量initialCapacity。
initicalCapacity = (需要存储的元素个数/负载因子) + 1。 负载因子默认为0.75。如果不确定存储的元素个数,设置初始大小为16(默认值)。
只有当HashMap中一次性添加一个集合putAll(),或者初始化指定容量大小时,才会通过算法计算容量大小,保证容量大小为2的n次幂。 put操作,如果容量为空,则初始化为16,容量不够,则只会简单的把当前容量扩大一倍。HashMap的容量因此能一直保持为2的N次幂大小。
ConcurrentHashMap:
ConcurrentHashMap的初始化时如果指定大小initialCapacity,
则以initialCapacity + (initialCapacity >>> 1) + 1 开始调整,计算出比它大的最近的2^n值作为初始大小
public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; }
JDK 8之后,ConcurrentHashMap的实现原理与之前有较大的变化:
它摒弃了Segment(锁段)的概念,改用了Synchronized 和 CAS原理来实现并发。它的底层与HashMap一致,仍然采用数组+链表+红黑树的结构。
第一次插入数据时,进行初始化数组initTable();
putVal方法中有一个无限循环:
for (Node<K,V>[] tab = table;;),只有操作成功才会跳出循环。
这其实是因为并发操作时,有时需要不断自旋等待。
/** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable();//初始化数组, else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //利用CAS算法,设置位置i的元素node if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED)//如果正在扩容,移动元素,则加入帮助扩容 tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) {//节点插入链表或者插入红黑树时,进行同步 if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }
获取几个相关参数的内存地址,使用CAS操作直接进行修改。
// Unsafe mechanics private static final sun.misc.Unsafe U; private static final long SIZECTL; private static final long TRANSFERINDEX; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); Class<?> k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class<?> ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class<?> ak = Node[].class; ABASE = U.arrayBaseOffset(ak);//获取数组第一个元素在内存中的偏移位置 int scale = U.arrayIndexScale(ak);//获取数组中元素的增量地址 //将arrayBaseOffset和arrayIndexScale配合使用,可以获取数组中每个元素的偏移位置 if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } }
相关的几个CAS操作的方法:
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); } static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); } static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }
EnumMap使用
EnumMap是专门为枚举类型量身定做的Map实现。
EnumMap要求其Key必须为Enum类型,它只能接收同一枚举类型的实例作为键值且不能为null。
EnumMap使用数组来存放与枚举类型对应的值,由于枚举类型实例的数量相对固定并且有限,所以使用EnumMap不会涉及到数组扩容,性能会更加高效。
相关推荐
java7-8中的 HashMap和ConcurrentHashMap全解析
java7-8中的 HashMap和ConcurrentHashMap全解析 如果你想了解底层的逻辑就来看看吧
HashMap& ConcurrentHashMap 深度解析
涵盖绝大部分HashMap与ConcurrentHashMap的面试题 附带答案
hashmap的底层及源码解析,很适合大家的学习,不要积分。
Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
下面小编就为大家带来一篇详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556
HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)实现,它通过散列算法将键值对映射到数组中。在HashMap中,每个键值对...
1.说一下 HashMap 的实现原理? 2.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现? 3.HashMap的put方法的具体流程? 4.HashMap的扩容操作是怎么实现的? 5.HashMap是怎么解决哈希冲突的? 6.什么是哈希?...
源码解析jdk8.0集合:HashMap的底层实现原理.pdf
HashMap的实现原理
源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf
今天小编就为大家分享一篇关于HashMap和HashTable底层原理以及常见面试题,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数 组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。 这是对于简单的键的情况,我们将其扩展到可以处理更加复杂...
HashMap底层原理.md
本文详述Java语言中的hashmap与concurrenthashmap,使用其他语言的朋友可做参考 首先我们先来看一下这几个类原码开头的部分 public class HashMap extends AbstractMap implements Map, Cloneable, Serializable ...
hashmap的C++实现,对于学习C++方面的很有用
HashMap底层原理