本文为博主原创文章,转载请注明出处:http://blog.csdn.net/eson_15/article/details/51154989
上一章总体分析了Map架构,并简单分析了一下AbstractMap源码,这一章开始我们将对Map的具体实现类进行详细的学习。本章先研究HashMap。依然遵循以下步骤:先对HashMap有个整体的认识,然后学习它的源码,深入剖析HashMap。
1.HashMap简介
首先看一下HashMap的继承关系
- java.lang.Object
- ↳ java.util.AbstractMap<K, V>
- ↳ java.util.HashMap<K, V>
-
- public class HashMap<K,V>
- extends AbstractMap<K,V>
- implements Map<K,V>, Cloneable, Serializable { }
我们可以看出,HashMap不仅继承了AbstractMap,而且实现了Map、Cloneable和Serializable接口,所以HashMap也可以序列化。另外,HashMap是非同步的,但是我们可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。即:
- Map map = Collections.synchronizedMap(new HashMap());
下面先总览一下HashMap都有哪些API,然后我们详细分析它们。
- void clear()
- Object clone()
- boolean containsKey(Object key)
- boolean containsValue(Object value)
- Set<Entry<K, V>> entrySet()
- V get(Object key)
- boolean isEmpty()
- Set<K> keySet()
- V put(K key, V value)
- void putAll(Map<? extends K, ? extends V> map)
- V remove(Object key)
- int size()
- Collection<V> values()
2.HashMap的数据结构
2.1存储结构
HashMap存储数据的数组定义如下,里面存放的是Entry<K,V>实体:
- transient Entry<K,V>[] table
HashMap的底层主要是基于数组和链表实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储位置的。HashMap中主要是通过key的hashCode来计算hash值,然后通过hash值选择不同的数组来存储。只要hashCode相同,计算出来的hash值就一样,如果存储对象多了,就有可能不同的对象计算出来的hash值是相同的,这就出现了所谓的hash冲突,解决hash冲突的方法很多,具体可以参见我这篇博客:数据结构与算法07 指哈希表。HashMap的底层是通过链表来解决hash冲突的。下面看一下它的存储结构图:
![](http://img.blog.csdn.net/20160415134451621?x-oss-process=image/resize,w_1400/format,webp)
图中紫色部分代表哈希表,其实就是哈希数组,数组的每个元素都是一个单链表的头结点,链表是用来解决hash冲突的,如果不同的key映射到了数组的同一位置,那么就将其放入单链表中。下面的图可能在代码的角度更能说明问题:
![](http://img.blog.csdn.net/20160415134456415?x-oss-process=image/resize,w_1400/format,webp)
下面我们阅读一下数组中存储的Entry实体类源码。
2.2Entry实体
-
-
-
-
-
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- int hash;
-
-
-
-
-
- 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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
- }
-
- public final String toString() {
- return getKey() + "=" + getValue();
- }
-
-
-
-
-
-
- void recordAccess(HashMap<K,V> m) {
- }
-
-
-
-
-
- void recordRemoval(HashMap<K,V> m) {
- }
- }
从Entry实体源码中可以看出,HashMap其实就是一个存储Entry的数组,Entry对象包含了键和值,其中next也是一个Entry对象,用来处理hash冲突的,形成一个链表。这样一来,我们对HashMap就有很好的理解了。下面我们详细分析HashMap中的源码。
3. HashMap源码分析(基于JDK1.7)
之前分析源码都是将所有源码全部贴上来,然后分析部分放到源码内部,这样看起来有点太多,一下子好几百行源码看的有点懵。这章开始采用分段式分析,将源码分分类,然后各部分突破,这样看起来更加清晰明朗。
3.1成员属性
先看看HashMap的几个关键属性:
-
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
-
-
- static final int MAXIMUM_CAPACITY = 1 << 30;
-
-
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
-
- static final Entry<?,?>[] EMPTY_TABLE = {};
-
-
- transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
-
-
- transient int size;
-
-
- int threshold;
-
-
- final float loadFactor;
-
-
- transient int modCount;
我们主要来看看loadFactor属性,loadFactor表示Hash表中元素的填满程度。
若加载因子设置过大,则填满的元素越多,无疑空间利用率变高了,但是冲突的机会增加了,冲突的越多,链表就会变得越长,那么查找效率就会变得更低;
若加载因子设置过小,则填满的元素越少,那么空间利用率变低了,表中数据将变得更加稀疏,但是冲突的机会减小了,这样链表就不会太长,查找效率变得更高。
这看起来有点绕口,我举个简单的例子,如果数组容量为100,加载因子设置为80,即装满了80个才开始扩容,但是在装的过程中,可能有很多key对应相同的hash值,这样就会放到同一个链表中(因为没到80个不能扩容),这样就会导致很多链表都变得很长,也就是说,不同的key对应相同的hash值比数组填满到80个更加容易出现。
但是如果设置加载因子为10,那么数组填满10个就开始扩容了,10个相对来说是很容易填满的,而且在10个内出现相同的hash值概率比上面的情况要小的多,一旦扩容之后,那么计算hash值又会跟原来不一样,就不会再冲突了,这样保证了链表不会很长,甚至就一个表头都有可能,但是空间利用率很低,因为始终有很多空间没利用就开始扩容。
因此,就需要在“减小冲突”和“空间利用率”之间寻找一种平衡,这种平衡就是数据结构中有名的“时-空”矛盾的平衡。如果机器内存足够,并且想要提高查询速度的话可以将加载因子设置小一点;相反如果机器内存紧张,并且对查询速度没什么要求的话可以将加载因子设置大一点。一般我们都使用它的默认值,即0.75。
3.2构造方法
下面看看HashMap的几个构造方法:
-
-
- 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;
-
- threshold = initialCapacity;
- init();
- }
-
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
-
- public HashMap() {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- }
-
-
- public HashMap(Map<? extends K, ? extends V> m) {
- this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
- DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
- inflateTable(threshold);
-
- putAllForCreate(m);
- }
我们可以看到,在构造HashMap的时候,如果我们指定了加载因子和初始容量的话就调用第一个构造方法,否则就用默认的。默认的初始容量为16加载因子为0.75。
3.3存取方法
存取部分重点分析一下put和get方法,因为这两个方法也是最常用的。其他的存取方法,我放到代码中分析。首先看看HashMap中是如何存储数据的,看put方法:
- public V put(K key, V value) {
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
-
-
- if (key == null)
- return putForNullKey(value);
-
- int hash = hash(key);
-
- int i = indexFor(hash, table.length);
-
-
- 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++;
-
- addEntry(hash, key, value, i);
- return null;
- }
我们下面一步步分析put方法内部都干了些啥:
首先检测table是不是为空table,如果是空table,说明并没有给table初始化,所以调用inflateTable(threadshold)方法给table初始化。该方法如下:
-
- private void inflateTable(int toSize) {
-
- int capacity = roundUpToPowerOf2(toSize);
-
- threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
- table = new Entry[capacity];
- initHashSeedAsNeeded(capacity);
- }
-
- private static int roundUpToPowerOf2(int number) {
-
- return number >= MAXIMUM_CAPACITY
- ? MAXIMUM_CAPACITY
-
- : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
- }
在inflateTable方法内,首先初始化数组容量大小,数组容量永远是2的幂(下面会分析为什么要这样)。所以调用roundUpToPowerOf2方法将传进来的容量转换成最接近2的次幂的值,然后重新计算阈值threadshold = 容量 x 加载因子,最后初始化table。所以刚开始初始化table不是在HashMap的构造函数里,因为构造函数中仅仅简单的将传进去的容量作为阈值。真正初始化table是在第一次往HashMap中put数据的时候。
初始化好了table后,就开始往table中存入数据了,table中存的是Entry实体,而put方法传进来的是key和value,所以接下来要做两件事:
1. 找到table数组中要存入的位置;
2. 将key和value封装到Entry中存入。
我们再回到put方法中,先来分析第一步,找存储的位置就要依靠key的值了,因为需要用key的值来计算hash值,根据hash值来决定在table中的位置。首先当key为null时,调用putForNullKey方法,该方法内部实现如下:
-
- private V putForNullKey(V value) {
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
-
- addEntry(0, null, value, 0);
- return null;
- }
从方法中可以看出,null的hash值为0,所以首先会定位到table[0]处,然后依次查询是否有key==null的键,如果有,将对应的value用新的value值取代,同时返回旧的value值。如果没有key==null的键,那么调用addEntry方法,将空键和值封装到Entry中放到table[0]的位置,addEntry方法如下:
-
- void addEntry(int hash, K key, V value, int bucketIndex) {
- if ((size >= threshold) && (null != table[bucketIndex])) {
- resize(2 * table.length);
- hash = (null != key) ? hash(key) : 0;
- bucketIndex = indexFor(hash, table.length);
- }
-
- createEntry(hash, key, value, bucketIndex);
- }
-
- void createEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
-
- table[bucketIndex] = new Entry<>(hash, key, value, e);
-
- size++;
- }
从该方法中可以看出,第一个参数是hash值,中间两个是key和value,最后一个是插入table的索引位置。插入之前先判断容量是否足够,若不够,HashMap中是2倍扩容。若够了,addEntry中先计算hash值,然后通过调用indexFor方法返回在索引的位置,这两个方法如下:
- final int hash(Object k) {
- int h = hashSeed;
- if (0 != h && k instanceof String) {
- return sun.misc.Hashing.stringHash32((String) k);
- }
-
- h ^= k.hashCode();
-
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
-
- static int indexFor(int h, int length) {
-
- return h & (length-1);
- }
indexFor方法返回索引的位置,里面只做了一件事:h & (length-1)。这究竟做了什么?为什么这句能解释容量必须为2的幂呢?我们详细分析下:
首先,h & (length-1)相当于h & length,但是h % length效率比较低(HashTable中是这儿干的)。为啥h & (length-1)相当于h % length呢?现在假设length为2的幂,那么length就可以表示成100......00的形式(表示至少1个0),那么length-1就是01111....11。对于任意小于length的数h来说,与01111...11做&后都是h本身,对于h=length来说,&后结果为0,对于大于length的数h,&过后相当于h-j*length,也就是h % length。这也就是为啥容量必须为2的幂了,为了优化,好做&运算,效率高。
其次,length为2的次幂的话,是偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h & (length-1)的最后一位可能为0也可能为1(取决于h的值),即结果可能为奇数,也可能为偶数,这样便可以保证散列的均匀性,即均匀分布在数组table中;而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h & (length-1)的最后一位肯定为0,级只能为偶数,这样任何hash值都会被映射到数组的偶数下标位置上,这便浪费了近一半的空间!因此,length去2的整数次幂,也是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀的散列。
再回到addEntry方法中,接下来就调用createEntry方法在table数组适当的位置开创一个Entry了,new Entry的时候,将next置为原本在该位置的Entry即可,这样,原来的Entry就挂到现在的Entry上了,以后只要在该位置新new一个Entry,就将原来的挂上去,这样一个挂一个,形成了一个链表。但是table中永远存储的是最新的Entry,并非一个真正的链表数据结构,只是这么多Entry是一个个连在一起的,跟链表很像而已。
现在往上回到put方法,我们刚刚分析完了key==null的情况,接着往下走,下面其实跟刚刚分析的一样了,先计算hash值,然后找到在table中的位置,然后开始判断是否已经有相同的key的Entry放在那了,如果有,用新的value取代旧的value,如果没有,用传进来的key和value新new一个Entry放到table中,并与原来的Entry挂上。过程跟上面分析的一模一样,唯一不同的就是key!=null。这里就不再赘述了。
下面再看看HashMap中读取数据的get方法:
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- Entry<K,V> entry = getEntry(key);
-
- return null == entry ? null : entry.getValue();
- }
-
- private V getForNullKey() {
- if (size == 0) {
- return null;
- }
- for (Entry<K,V> e = table[0]; e != null; e = e.next) {
- if (e.key == null)
- return e.value;
- }
- return null;
- }
-
- final Entry<K,V> getEntry(Object key) {
- if (size == 0) {
- return null;
- }
-
- int hash = (key == null) ? 0 : hash(key);
- for (Entry<K,V> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
-
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- }
- return null;
- }
有了对put方法的理解,这段get方法应该就很容易了。从源码中更可以看出,从HashMap中get元素时,先计算key的hashCode,找到数组中国对应的位置,然后通过key的equals在对应位置的链表中找到需要的元素。这里就不再赘述了。
3.4其他方法
上面我们重点分析了HashMap中的存取方法,当然HashMap中还有其他很多方法,如remove、containsXXX等,以及与迭代器和序列化相关的方法等等。该部分方法的解析全部放在源码里了。源码如下:
-
- public int size() {
- return size;
- }
-
-
- public boolean isEmpty() {
- return size == 0;
- }
-
-
- public boolean containsKey(Object key) {
- return getEntry(key) != null;
- }
-
-
- private void putForCreate(K key, V value) {
-
- int hash = null == key ? 0 : hash(key);
- int i = indexFor(hash, table.length);
-
-
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {
- Object k;
-
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) {
- e.value = value;
- return;
- }
- }
-
- createEntry(hash, key, value, i);
- }
-
-
- private void putAllForCreate(Map<? extends K, ? extends V> m) {
- for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
- putForCreate(e.getKey(), e.getValue());
- }
-
-
- void resize(int newCapacity) {
- Entry[] oldTable = table;
- int oldCapacity = oldTable.length;
-
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
-
-
- Entry[] newTable = new Entry[newCapacity];
-
- transfer(newTable, initHashSeedAsNeeded(newCapacity));
- table = newTable;
-
- threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
- }
-
-
- void transfer(Entry[] newTable, boolean rehash) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e : table) {
- while(null != e) {
- Entry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
- int i = indexFor(e.hash, newCapacity);
-
- e.next = newTable[i];
- newTable[i] = e;
- e = next;
- }
- }
- }
-
-
-
- public void putAll(Map<? extends K, ? extends V> m) {
-
- int numKeysToBeAdded = m.size();
- if (numKeysToBeAdded == 0)
- return;
-
- if (table == EMPTY_TABLE) {
- inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
- }
-
-
- if (numKeysToBeAdded > threshold) {
-
- int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
- if (targetCapacity > MAXIMUM_CAPACITY)
- targetCapacity = MAXIMUM_CAPACITY;
- int newCapacity = table.length;
- while (newCapacity < targetCapacity)
- newCapacity <<= 1;
- if (newCapacity > table.length)
- resize(newCapacity);
- }
-
- for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
- put(e.getKey(), e.getValue());
- }
-
-
- public V remove(Object key) {
- Entry<K,V> e = removeEntryForKey(key);
- return (e == null ? null : e.value);
- }
-
-
- final Entry<K,V> removeEntryForKey(Object key) {
- if (size == 0) {
- return null;
- }
- int hash = (key == null) ? 0 : hash(key);
- int i = indexFor(hash, table.length);
- Entry<K,V> prev = table[i];
- Entry<K,V> e = prev;
-
- while (e != null) {
- Entry<K,V> next = e.next;
- Object k;
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) {
- modCount++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
-
- return e;
- }
-
-
- final Entry<K,V> removeMapping(Object o) {
- if (size == 0 || !(o instanceof Map.Entry))
- return null;
-
- Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
- Object key = entry.getKey();
- int hash = (key == null) ? 0 : hash(key);
- int i = indexFor(hash, table.length);
- Entry<K,V> prev = table[i];
- Entry<K,V> e = prev;
-
- while (e != null) {
- Entry<K,V> next = e.next;
- if (e.hash == hash && e.equals(entry)) {
- modCount++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
-
- return e;
- }
-
-
- public void clear() {
- modCount++;
- Arrays.fill(table, null);
- size = 0;
- }
-
-
- public boolean containsValue(Object value) {
- if (value == null)
- return containsNullValue();
-
- Entry[] tab = table;
- for (int i = 0; i < tab.length ; i++)
- for (Entry e = tab[i] ; e != null ; e = e.next)
- if (value.equals(e.value))
- return true;
- return false;
- }
-
-
- private boolean containsNullValue() {
- Entry[] tab = table;
- for (int i = 0; i < tab.length ; i++)
- for (Entry e = tab[i] ; e != null ; e = e.next)
- if (e.value == null)
- return true;
- return false;
- }
-
-
- public Object clone() {
- HashMap<K,V> result = null;
- try {
- result = (HashMap<K,V>)super.clone();
- } catch (CloneNotSupportedException e) {
-
- }
- if (result.table != EMPTY_TABLE) {
- result.inflateTable(Math.min(
- (int) Math.min(
- size * Math.min(1 / loadFactor, 4.0f),
-
- HashMap.MAXIMUM_CAPACITY),
- table.length));
- }
- result.entrySet = null;
- result.modCount = 0;
- result.size = 0;
- result.init();
- result.putAllForCreate(this);
-
- return result;
- }
-
-
- private abstract class HashIterator<E> implements Iterator<E> {
- Entry<K,V> next;
- int expectedModCount;
- int index;
- Entry<K,V> current;
-
- HashIterator() {
- expectedModCount = modCount;
- if (size > 0) {
- Entry[] t = table;
- while (index < t.length && (next = t[index++]) == null)
- ;
- }
- }
-
- public final boolean hasNext() {
- return next != null;
- }
-
- final Entry<K,V> nextEntry() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- Entry<K,V> e = next;
- if (e == null)
- throw new NoSuchElementException();
-
- if ((next = e.next) == null) {
- Entry[] t = table;
- while (index < t.length && (next = t[index++]) == null)
- ;
- }
- current = e;
- return e;
- }
-
- public void remove() {
- if (current == null)
- throw new IllegalStateException();
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- Object k = current.key;
- current = null;
- HashMap.this.removeEntryForKey(k);
- expectedModCount = modCount;
- }
- }
-
- private final class ValueIterator extends HashIterator<V> {
- public V next() {
- return nextEntry().value;
- }
- }
-
- private final class KeyIterator extends HashIterator<K> {
- public K next() {
- return nextEntry().getKey();
- }
- }
-
- private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
- public Map.Entry<K,V> next() {
- return nextEntry();
- }
- }
-
-
- Iterator<K> newKeyIterator() {
- return new KeyIterator();
- }
- Iterator<V> newValueIterator() {
- return new ValueIterator();
- }
- Iterator<Map.Entry<K,V>> newEntryIterator() {
- return new EntryIterator();
- }
-
- private transient Set<Map.Entry<K,V>> entrySet = null;
-
-
-
-
-
-
-
-
-
- public Set<K> keySet() {
- Set<K> ks = keySet;
- return (ks != null ? ks : (keySet = new KeySet()));
- }
-
- private final class KeySet extends AbstractSet<K> {
- public Iterator<K> iterator() {
- return newKeyIterator();
- }
- public int size() {
- return size;
- }
- public boolean contains(Object o) {
- return containsKey(o);
- }
- public boolean remove(Object o) {
- return HashMap.this.removeEntryForKey(o) != null;
- }
- public void clear() {
- HashMap.this.clear();
- }
- }
-
-
-
-
-
-
-
-
-
- public Collection<V> values() {
- Collection<V> vs = values;
- return (vs != null ? vs : (values = new Values()));
- }
-
- private final class Values extends AbstractCollection<V> {
- public Iterator<V> iterator() {
- return newValueIterator();
- }
- public int size() {
- return size;
- }
- public boolean contains(Object o) {
- return containsValue(o);
- }
- public void clear() {
- HashMap.this.clear();
- }
- }
-
-
-
-
-
-
-
-
-
-
- public Set<Map.Entry<K,V>> entrySet() {
- return entrySet0();
- }
-
- private Set<Map.Entry<K,V>> entrySet0() {
- Set<Map.Entry<K,V>> es = entrySet;
- return es != null ? es : (entrySet = new EntrySet());
- }
-
- private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
- public Iterator<Map.Entry<K,V>> iterator() {
- return newEntryIterator();
- }
- public boolean contains(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry<K,V> e = (Map.Entry<K,V>) o;
- Entry<K,V> candidate = getEntry(e.getKey());
- return candidate != null && candidate.equals(e);
- }
- public boolean remove(Object o) {
- return removeMapping(o) != null;
- }
- public int size() {
- return size;
- }
- public void clear() {
- HashMap.this.clear();
- }
- }
-
-
- private void writeObject(java.io.ObjectOutputStream s)
- throws IOException
- {
-
- s.defaultWriteObject();
-
-
- if (table==EMPTY_TABLE) {
- s.writeInt(roundUpToPowerOf2(threshold));
- } else {
- s.writeInt(table.length);
- }
-
-
- s.writeInt(size);
-
-
-
-
-
-
-
-
- if (size > 0) {
- for(Map.Entry<K,V> e : entrySet0()) {
- s.writeObject(e.getKey());
- s.writeObject(e.getValue());
- }
- }
- }
-
- private static final long serialVersionUID = 362498820763181265L;
-
- private void readObject(java.io.ObjectInputStream s)
- throws IOException, ClassNotFoundException
- {
-
- s.defaultReadObject();
- if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
- throw new InvalidObjectException("Illegal load factor: " +
- loadFactor);
- }
-
-
- table = (Entry<K,V>[]) EMPTY_TABLE;
-
-
- s.readInt();
-
-
- int mappings = s.readInt();
- if (mappings < 0)
- throw new InvalidObjectException("Illegal mappings count: " +
- mappings);
-
-
- int capacity = (int) Math.min(
- mappings * Math.min(1 / loadFactor, 4.0f),
-
- HashMap.MAXIMUM_CAPACITY);
-
-
- if (mappings > 0) {
- inflateTable(capacity);
- } else {
- threshold = capacity;
- }
-
- init();
-
-
- for (int i = 0; i < mappings; i++) {
- K key = (K) s.readObject();
- V value = (V) s.readObject();
- putForCreate(key, value);
- }
- }
-
-
- int capacity() { return table.length; }
- float loadFactor() { return loadFactor; }
3.HashMap 遍历方式
HashMap的遍历方式比较单一,一般分两步走:
1. 获得Entry或key或value的Set集合;
2. 通过Iterator迭代器遍历此Set集合。
3.1遍历HashMap的Entry
-
-
- String key = null;
- Integer integ = null;
- Iterator iter = map.entrySet().iterator();
- while(iter.hasNext()) {
- Map.Entry entry = (Map.Entry)iter.next();
-
- key = (String)entry.getKey();
- integ = (Integer)entry.getValue();
- }
3.2遍历HashMap的key
-
-
- String key = null;
- Integer integ = null;
- Iterator iter = map.keySet().iterator();
- while (iter.hasNext()) {
-
- key = (String)iter.next();
-
- integ = (Integer)map.get(key);
- }
3.3遍历HashMap的value
-
-
- Integer value = null;
- Collection c = map.values();
- Iterator iter= c.iterator();
- while (iter.hasNext()) {
- value = (Integer)iter.next();
- }
HashMap的遍历比较简单,主要是通过Iterator迭代器来实现,但是方式有三种,都可以最终获得value值。
最后给大家分享一个链接:https://www.cs.usfca.edu/~galles/visualization/OpenHash.html 。可以很直观的看到HashMap添加和删除数据的过程。帮助我们更好的理解HashMap。
HashMap就讨论到这吧,如有错误,欢迎留言指正~
转载:http://blog.csdn.net/eson_15/article/details/51158865