java.util.HashMap 解析

     HashMap 是我们经常使用的一种数据结构。工作中会经常用到，面试也会总提到这个数据结构，找工作的时候，”HashTable 和HashMap的区别“被问到过没有？

     本文会从原理，JDK源码，项目使用多个角度来分析HashMap。

 

     1.HashMap是什么

       JDK文档中如是说”基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）不保证映射的顺序“

       里面大致包含如下意思：

       HashMap是Map的实现，因此它内部的元素都是K-V（键，值）组成的。

       HashMap内部元素是无序的

 

     2.jdk中如何实现一个HashMap

        HashMap在java.util包下，我们平时使用的类，有大部分都是这个包或者其子包的类

        JDK中实现类的定义

 

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

       它实现了Map接口

       通常我们这么使用HashMap

 

Map<Integer,String> maps=new HashMap<Integer,String>();
maps.put(1, "a");
maps.put(2, "b");

 上面代码新建了一个HashMap并且往里插入了两个数据，这里不接受基本数据类型来做K,V

如果你这么写的话，就会出问题了

Map<int,double> maps=new HashMap<int,double>();

 

   上面例子很简单可是你知道内部他们怎么实现的吗？

   我们来看看HashMap的构造方法

 

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

 

都知道HashMap是个变长的数据结构，看了上面的构造方法可能你并不会认为它有那么神了。

DEFAULT_LOAD_FACTOR   //默认加载因子，如果不制定的话是0.75

 

DEFAULT_INITIAL_CAPACITY //默认初始化容量，默认是16

 

threshold //阈（yu）值 根据加载因子和初始化容量计算得出

    因此我们知道了，如果我们调用无参数的构造方法的话，我们将得到一个16容量的数组

    数组是定长的，如何用一个定长的数据来表示一个不定长的数据呢，答案就是找一个更长的

    下面来看看put方法是怎么实现的

 public V put(K key, V value) {
        if (key == null) //键为空的情况，HashMap和HashTable的一个区别
            return putForNullKey(value);
        int hash = hash(key.hashCode()); //根据键的hashCode算出hash值
        int i = indexFor(hash, table.length); //根据hash值算出究竟该放入哪个数组下标中
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整个for循环实现了如果存在K那么就替换V
            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;
    }

 区区十几行代码，通过我添加的注释看懂并不难，细心的话可能会发现这里并没有体现变长的概念，如果我数据大于之前的容量的怎么继续添加呀，答案就在addEntry方法中

 void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

 这里显示了如果当前size>threshold的话那么就会扩展当前的size的两倍,如何扩展？

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);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

 new 一个新的数组，将旧数据转移到新的数组中，并且重新计算阈值，如何转移数据？

 void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                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);
            }
        }
    }

 根据hash值，和新的容量重新计算数据下标。天呀，太麻烦了吧。

 到此为止我们知道了新建一个HashMap和添加一个HashMap之后源代码中都干了什么。

     3.hashcode你懂它不

      HashMap是根据hashcode的来进行计算hash值的，equals方法默认也是通过hashcode来进行比较的

      hashCode到底是个什么东西呢？

      我们跟踪JDK源码到Object结果JDK确给了我们一个下面的本地方法

public native int hashCode();

     通过方法我们只能知道hashcode 是一个int值。

     疑问更加多了，首先它如何保证不同对象的hashcode 值不一样呢，

     既然hashcode是一个整形的，那么它最多的应该只能表示Integer.maxValue个值，

那么当大于这么多值的情况下这些对象的值又该如何表示呢。

     要理解这些东西需要从操作系统说起了

     //TODO 时间关系，后面再补

 

     4.HashMap的优缺点

     优点：超级快速的查询速度，如果有人问你什么数据结构可以达到O(1)的时间复杂度，没错是HashMap

             动态的可变长存储数据（和数组相比较而言）

     缺点：需要额外计算一次hash值

             如果处理不当会占用额外的空间

 

     5.如果更加高效的使用HashMap

       添加

       前面我们知道了添加数据的时候，如果当前数据的个数加上1要大于hashmap的阈值的话，那么数组就会进行一个*2的操作。并且从新计算所有元素的在数组中的位置。

       因此如果我们要添加一个1000个元素的hashMap，如果我们用默认值那么我么需要额外的计算多少次呢

       当大于16*0.75=12的时候，需要从新计算 12次

       当大于16*2*0.75=24的时候，需要额外计算 24次

       ……

       当大于16*n*0.75=768的时候，需要额外计算 768次

       所以我们总共在扩充过程中额外计算12+24+48+……+768次

       因此强力建议我们在项目中如果知道范围的情况下，我们应该手动指定初始大小 像这样

 

Map<Integer,String> maps=new HashMap<Integer,String>(1000);

 

       删除

       JDK中如下方式进行删除

 public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        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;
    }

   根据上面代码我们知道了，如果删除是不进行了数组容量的重新定义的。所以，如果你有1000个元素的HashMap就算你最后删除只剩下一个了，你在内存中依然还有大于1000个容量，其中大于999个是空的。 为什么是大于因为扩容之后的HashMap实际容量大于1000个。

 因此如果我们项目中有很大的HashMap，删除之后却很小了，我们还是弄一个新的小的存它 吧。

 

     6.HashMap同步

       如果HashMap在多线程下会出现什么问题呢

       我们知道HashMap不是线程安全的（HashMap和HashTable的另外一个区别），如果我们也想要在多线程的环境下使用它怎么办呢？

       也许你会说不是有HashTable吗？那我们就试试

public class MyThread extends Thread { // 线程类
	private Map<Integer, String> maps; // 多线程处理的map

	public MyThread(Map<Integer, String> maps) {
		this.maps = maps;
	}

	@Override
	public void run() {
		int delNumber = (int) (Math.random() * 10000);//随即删除的key
		op(delNumber);
	}

	public void op(int delNumber) {
		Iterator<Map.Entry<Integer, String>> t = maps.entrySet().iterator();
		while (t.hasNext()) {
			Map.Entry<Integer, String> entry = t.next();
			int key = entry.getKey();
			if (key == delNumber) { //看下key是否是需要删除的key是的话就删除
				maps.remove(key);
				break;
			}
		}
	}

}

 

public class HashMapTest {
	public static void main(String[] args) {
		testSync();
	}

	public static void testSync(){
		Map<Integer, String> maps = new Hashtable<Integer, String>(10000);
//		Map<Integer, String> maps = new HashMap<Integer, String>(10000);
//		Map<Integer, String> maps = new ConcurrentHashMap<Integer, String>(10000);
		for (int i = 0; i < 10000; i++) {
			maps.put(i, "a");
		}
		for(int i=0;i<10;i++){
			new MyThread(maps).start();
		}
	}

}

 我们使用HashTable来运行试试，不一会就出现了如下错误信息

Exception in thread "Thread-6" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-4" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-2" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-1" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-8" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-9" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
Exception in thread "Thread-5" java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1031)
	at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22)
	at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16)
ERROR: JDWP Unable to get JNI 1.2 environment, jvm->GetEnv() return code = -2
JDWP exit error AGENT_ERROR_NO_JNI_ENV(183):  [../../../src/share/back/util.c:820]

 不是说是安全的不？为什么会出现这个问题呢，继续看源代码

public T next() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	    return nextElement();
	}

  当修改之后的计数器和期望的不一致的时候就会抛出异常了。对应于上面代码，线程1，遍历的时候假如有100个，本来删除之后就99个，但是线程2这段时间也删除了一个

所以实际只有98个了，线程1并不知道，当线程1调用next方法时候比较下结果不对，完了，数据不对了，老板要扣工资了，线程自己也解决不了，抛出去吧，别引起更大的问题了。

于是你得到了一个ConcurrentModificationException。

所以以后要注意了，HashTable,vector都不是绝对线程安全的了，所以我们需要将maps加上同步

public void op(int delNumber) {
		synchronized (maps) {
			Iterator<Map.Entry<Integer, String>> t = maps.entrySet().iterator();
			while (t.hasNext()) {
				Map.Entry<Integer, String> entry = t.next();
				int key = entry.getKey();
				if (key == delNumber) { // 看下key是否是需要删除的key是的话就删除
					maps.remove(key);
					break;
				}
			}
		}
	}

 synchronized(maps)加上之后就不会出现问题了，就算你用的是HashMap都不会出问题。

其实JDK中在早在1.5之后又了ConcurrentHashMap了这个类你可以放心的在多线程下使用并且不需要加任何同步 了。

 

评论

2 楼 Nabulio 2016-08-12  

1 楼 vrljx 2014-01-15  

非常清楚，很有帮助，十分感谢