- 浏览: 28311 次
- 来自: ...
文章分类
最新评论
1. 参数介绍
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The next size value at which to resize (capacity * load factor). * @serial */ int threshold; /** * The load factor for the hash table. * * @serial */ final float loadFactor; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient volatile int modCount;
Entry[] table:
用于存放Entry(key-value)的数组。Entry类实际上是个链结构,正因如此,对于table[i] (0 <= i <= table.length - 1),里面可以存放任意数量的Entry。(看过hash算法的应该不陌生)
capacity:
该值并不是变量,等于table.length。DEFAULT_INITIAL_CAPACITY是改参数的默认值。该参数必须是2的n(n是自然数)次方,我猜是选用了移位算法作为Hash的缘故。 MAXIMUM_CAPACITY是该参数的最大值。
size:
该参数记录HashMap中Entry的数量。当该值超过threshold的时候,HashMap会进行扩容并且rehash操作。
loadFactor:
一个算法参数,决定了HashMap何时会进行扩容和rehash。DEFAULT_LOAD_FACTOR是改参数的默认值。 该值越大,table所占空间就越小,Entry多的时候性能就越差。反之,table所占空间就越大,性能也就越好。
threshold:
该参数等于capacity*loadFactor。当size超过该值时,HashMap会进行扩容并且rehash操作。
modCount:
2. HashMap.Entry
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }
该类是用于保存HashMap中key-value的数据结构,采用单向链。
3. 重要的方法
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
对某个h值进行hash计算。该方法一般用于对key对象的hashCode()调用。
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
根据上面方法生成的hash值计算table中所处的位置。因为用的是&(并操作),保证了结果小于等于table的length。
/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { //将新Entry插入到table中指定位置,该位置原有链会作为该Entry的next(参考Entry的构造方法) Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //如果size超过threshold,扩容 if (size++ >= threshold) resize(2 * table.length); }
/** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果已经是最大容量,则将threshold设置为最大并返回 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; //将oldTable里面的所有元素hash到newTable transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; //循环处理oldTable里面每个Entry链 for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; //循环处理链里面的每个Entry,重新计算Entry所在newTable的位置,并把该Entry插入到newTable[i]的最前端 do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
4. 构造HashMap
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); // Find a power of 2 >= initialCapacity int capacity = 1; //保证capacity是2的n次方。 while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; //该方法是空方法,供继承类实现额外操作。 init(); }
5. put
/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { //空key处理 if (key == null) return putForNullKey(value); //生成key所对应的hash int hash = hash(key.hashCode()); //根据hash获得table中所在的位置 int i = indexFor(hash, table.length); //链式搜索是否已经存在相同key的Entry,如果存在,则替换掉oldValue并返回oldValue for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //插入新的Entry到i位置 addEntry(hash, key, value, i); return null; }
相关推荐
精确的版本号是jdk-8u181。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
精确的版本号是jdk-7u80。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
精确的版本号是jdk-6u45。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。 想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
源码解析jdk8.0集合:HashMap的底层实现原理.pdf
HashMap源码(JDK1.7,含注释)
jdk 1.7 HashMap源码
本人源码阅读理解, 基于jdk1.7 和jdk 1.8的java HashMap源码的理解, 希望对你理解java源码有作用
jdk源码学习 JavaSourceLearn 版本号 版本 corretto-1.8.0_275 方式 逐步阅读源码添加注释、notes文件夹添加笔记 计划学习任务计划 标题为包名,后面序号为优先级1-4,优先级递减 java.lang Object 1 String 1 ...
1、此HashMap类采用java jdk中HashMap的实现方式。2、相比网站上发布过的hashtable之类的源码:。此HashMap寻址方法是拉链法.比开放寻址法对连续内存要求更低。哈希函数用的是java中String.hashCode()算法(经实际验证...
java学习笔记,包括JVM,并发,JDK一些工具的源码,spring,hashMap实现源码分析
首先,我们了解一下HashMap的底层结构历史,在JDK1.8之前采用的是数组+链表的数据结构来存储数据,是不是觉得很熟悉,没错这玩意在1.8之前的结构就和HashTable一样都是采用数组+链表,同样也是通过链地址法(这里简称...
这又是看了忘忘了看系列之一,今天有空写个文档记录下,希望能从JDK源码中慢慢悟出他们优秀的思想。本文主要记录以下几个方面。 1、HashMap的继承、实现结构 2、HashMap的构造函数们及属性们 ...
java hashmap 源码
源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf
计算机后端-Java-Java核心基础-第25章 集合02 12. HashMap在JDK8中的源码分析.avi
计算机后端-Java-Java核心基础-第25章 集合02 11. HashMap在JDK7中的源码分析.avi