Java容器 HashMap与HashSet的学习

浏览数：23 / 时间：2015年06月08日 

Java学习中，看到HashMap，HashSet类，本着不止要停留在用的层面( 很多公司面试都要问底层 )，学习了JDK源码，记录下笔记。

源码来自jdk1.7下的src.zip

HashMap是一种键值对类型，它提供一种Key-Value对应保存的数据结构，实现了Map接口，其中key的值唯一，即一个key某一时刻只能映射到唯一的值。

看其中几个成员（没列全）

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
final float loadFactor;
int threshold;

table为一个数组结构，每对映射就是放在这里了

Entry<K,V>实现Map.Entry，也就是Map中的一个key-value键值对，看其究竟(还包含了其他方法，这里先略去)

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;


        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        …

Entry是HashMap的内部类，它的成员有key，value，hash，这个next是链式结构，Entry包含了基本映射hashCode()方法，ok清楚它的组成了

HashMap的数据结构也就是

技术分享

我们现在关心HashMap的put(K key, V value)方法

public V put(K key, V value) {
        if (table == EMPTY_TABLE) { //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) {//如果要插入的entry的key出现过，则替换成新插入entry的value，并返回oldValue
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//hash值相等可能是碰撞，判断相等还可能重写了equals方法，所以加上||
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);//加入到链表头部
        return null;
    }
以上可以看出，根据key来决定每个Entry的存储位置，可以把value当成key的附属，看看hash()方法 

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // 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);
    }
也就是说通过一个哈希函数（至于hashCode与得到h的做法不清楚……），将key映射到一个int型的hash值，然后通过indexFor就确定了key在table数组中的下标 

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }
这个length是2的次幂，解决前面hash值比数组长度还大的情况。

再看看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对是在链表的头部，可以看上面的Entry构造函数
    	//e是之前的head，然后在new Entry时作为了next。
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
}
可以看到，如果不同的key映射到相同的hash值，对调用addEntry，然后采用了链地址法作为处理冲突的方法，新对象放在了链表头部

同时，当加入的entry数量到达threshold时，table会被resize， resize中有个transfer方法，用来将旧的table的内容拷贝到新的table中。table的大小加倍

<span style="font-size:14px;">void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//如果已达到 1 << 30,就无法再扩容了
            threshold = Integer.MAX_VALUE;//(1 << 31) - 1
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable,initHashSeedAsNeeded(newCapacity));  // 把当前table内容拷贝到新的table里
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新计算threshold
}</span>
至此，HashMap的整个put过程已经讲完。

get方法：

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
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)]; 
        	// table[indexFor(hash, table.length)] 就是将indexFor运算得到的值直接映射到数组的索引
             e != null;
        		// 搜索该 Entry 链的下一个 Entry
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

查找的过程：找到映射的点之后再和链表里的元素逐个比较，保证找到目标值。因为是hash表，会存在多个值映射到同一个index里面，所以这里还要和链表里的元素做对比。

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能，即table数组中没有链表下拉的情况。

简单总结HashMap：

HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。

HashSet的实现

对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层采用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，查看 HashSet 的源代码，可以看到如下代码：

public class HashSet<E> 
	 extends AbstractSet<E> 
	 implements Set<E>, Cloneable, java.io.Serializable 
 { 
	 // 使用 HashMap 的 key 保存 HashSet 中所有元素
	 private transient HashMap<E,Object> map; 
	 // 定义一个虚拟的 Object 对象作为 HashMap 的 value 
	 private static final Object PRESENT = new Object(); 
	 ... 
	 // 初始化 HashSet，底层会初始化一个 HashMap 
	 public HashSet() 
	 { 
		 map = new HashMap<E,Object>(); 
	 } 
	 // 以指定的 initialCapacity、loadFactor 创建 HashSet 
	 // 其实就是以相应的参数创建 HashMap 
	 public HashSet(int initialCapacity, float loadFactor) 
	 { 
		 map = new HashMap<E,Object>(initialCapacity, loadFactor); 
	 } 
	 public HashSet(int initialCapacity) 
	 { 
		 map = new HashMap<E,Object>(initialCapacity); 
	 } 
	 HashSet(int initialCapacity, float loadFactor, boolean dummy) 
	 { 
		 map = new LinkedHashMap<E,Object>(initialCapacity 
			 , loadFactor); 
	 } 
	 // 调用 map 的 keySet 来返回所有的 key 
	 public Iterator<E> iterator() 
	 { 
		 return map.keySet().iterator(); 
	 } 
	 // 调用 HashMap 的 size() 方法返回 Entry 的数量，就得到该 Set 里元素的个数
	 public int size() 
	 { 
		 return map.size(); 
	 } 
	 // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空，
	 // 当 HashMap 为空时，对应的 HashSet 也为空
	 public boolean isEmpty() 
	 { 
		 return map.isEmpty(); 
	 } 
	 // 调用 HashMap 的 containsKey 判断是否包含指定 key 
	 //HashSet 的所有元素就是通过 HashMap 的 key 来保存的
	 public boolean contains(Object o) 
	 { 
		 return map.containsKey(o); 
	 } 
	 // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap 
	 public boolean add(E e) 
	 { 
		 return map.put(e, PRESENT) == null; 
	 } 
	 // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素
	 public boolean remove(Object o) 
	 { 
		 return map.remove(o)==PRESENT; 
	 } 
	 // 调用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素
	 public void clear() 
	 { 
		 map.clear(); 
	 } 
	 ... 
 }

由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。

参考：疯狂Java

就只分析到这里了，lz第一次看jdk源码，有问题或指正可留言……










 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢