简介
HashMap是采用链表和位桶来来实现的,由于一个位桶存在元素太多会导致get效率低,因此在jdk1.8中采用的红黑树实现,当链表长度大于TREEIFY_THRESHOLD(值为8)时会转换为红黑树来提高查询效率。
HashMap是一种以键值对存储的框架,它是Map的实现类,提供了Map的基础操作,与HashTalbe不同的是HashMap不是线程安全的,key和value都是允许为null的;另外hashmap存储的内容顺序会变化的。
HashMap对与get和put操作提供了相对稳定的性能;如果注重Iteration迭代集合的性能,则不能设置初始化容量(capacity)太高或者负载因子(load factor)太低。影响HashMap性能的两个重要参数是初始化容量(initial capacity)和负载因子(load factor),初始化容量是至哈希表在创建时候的桶(bucket)的个数,负载因子是当哈希表放满的时候进行的增量系数,默认为0.75。
HashMap默认是线程不安全的 ,如果需要同步需要通过Cllections工具类进行包装:Map m = Collections.synchronizedMap(new HashMap(...));
示意图
纯手工画的,请容忍_!
关系图
使用示例
HashMap<Object, Object> hashMap = new HashMap<>(); //新增 hashMap.put("name","张三"); hashMap.put("age",18); //删除 hashMap.remove("name"); //修改 hashMap.replace("age",16); //查询 hashMap.get("age"); //判断是否包含 hashMap.containsKey("age"); hashMap.containsValue(18); //循环1 Set<Map.Entry<Object, Object>> entries = hashMap.entrySet(); for (Map.Entry<Object, Object> entry:entries){ System.out.println("key="+entry.getKey()+" value="+entry.getValue()); } //循环2 Set<Object> keys = hashMap.keySet(); for(Object key:keys){ System.out.println("key="+key+" value="+hashMap.get(key)); } //清除 hashMap.clear();
原理分析
HashMap的初始化
初始化内容主要是容量大(initialCapacity)小和负载因子(loadFactor)的设定,table下次扩容的极限值(threshold),new的时候并没有真正的初始化容器。
默认初始化-所有系数使用默认值,初始容量=16,负载因子=0.75
//默认初始化容量static final int DEFAULT_INITIAL_CAPACITY = 16;//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//链表对象数组transient Node<K,V>[] table;//加载因子final float loadFactor;//极限值,当键值对数量大于等于threshold,则触发扩容方法resize()//第一次初始化时候:threshold=(int)(loadFactor*initialCapacity),只有手动设置initialCapacity时候才需要第一次初始化//第二次初始化的时候:threshold=(threshold*loadFactor)//初始化后的扩容:newThr=threshold<<1,相当于threshold*2int threshold;public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
自定义初始化容量,其他参数使用默认值
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
定义初始化容量和负载因子
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //将初始化容量转换为2的n次幂 this.threshold = tableSizeFor(initialCapacity); }//将cap向上转化为2的n次幂,如cap=17转化后为32 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(key,value)分析
put操作
1、第一次新增键值对时候,首先进行内部Node<K,V>[] table初始化
2、新增一个键值对,如果key已经存在则进行替换原来value,如果不存在则进行新增。
public V put(K key, V value) { //放入键值对 //最后两个参数为 false表名修改已存在的值,否则不进行修改,最后一个true在LinkedHashMap使用 return putVal(hash(key), key, value, false, true); } //对key进行hash计算,获取hash值static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
//存放键值对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为空或者长度为0,则进行初始化,初始化在下面进行分析if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//计算key的下标(n-1)&hash,判断当前下标中是否已经有元素,没有则进行直接新增//key的下标算法(n-1)是table的最大下标,然后与hash进行与计算则获取最终下标,//这种下标计算不仅保证了下标在0-15之间的某个值,而且也保证了下标的均匀分布和计算效率if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);//如果当前下标已经存在元素则进行下列计算else { Node<K,V> e; K k; //如果已经存在相同的key,则将原来的元素赋值为e 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 { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果链表的长度大于等于7的时候将链表转化为红黑树(jdk1.8新增的) //因为如果存在大量数据的hash值相等,怎会产生很大的链表, //而链表的查询效率较低,所以在1.8版本后新增了红黑树结构。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //将链表转换为红黑树 treeifyBin(tab, hash); break; } //如果在链表的某个环节碰到相同的key则停止循环 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //已经存在相同的key,只需将新的value赋值给老的value即可 if (e != null) { // existing mapping for key V oldValue = e.value; //onlyIfabsent是用来决定是否覆盖已有的key的value,在hashmap中默认false if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount;//最终判断容器table的大小+1是否超过table的极限值threshold,如果超过则进行扩容//扩容的方式是newThr=threshold<<1,相当于threshold*2if (++size > threshold) resize(); afterNodeInsertion(evict);return null; }
resize分析
初始化table或者扩容的时候需要执行resize。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //如果原来的容量大于MAXIMUM_CAPACITY=1073741824则将threshold设为 //Integer.MAX_VALUE=2147483647 接近MAXIMUM_CAPACITY的两倍 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //否则设为newThr为原来的两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果原来的thredshold大于0则将容量设为原来的thredshold //在第一次带参数初始化时候会有这种情况 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //在默认无参数初始化会有这种情况 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; 如果原来的table有数据,则将数据复制到新的table中 if (oldTab != null) { //根据容量进行循环整个数组,将非空元素进行复制 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果链表只有一个,则进行直接赋值 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果是红黑树则进行红黑树操作 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //进行链表复制 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
treeifyBin将某个链表转为红黑树
hash是需要转化为红黑树的链表哈希
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }
putTreeVal红黑树新增
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; //获取树根 TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; // hashMap元素的hash值用来表示红黑树中节点数值大小 // 当前节点值小于根节点,dir = -1 // 当前节点值大于根节 http://www.cnblogs.com/mvilplss/p/7144146.html