Java中的HashMap浅析
在Java的集合框架中，HashSet，HashMap是用的比较多的一种，顺序结构的ArrayList、LinkedList这种也比较多，而像那几个线程同步的容器用的比较少，像Vector和HashTable，因为这两个线程同步的容器已经不被JDK推荐使用了，这是个比较老式的线程安全的容器，JDK比较推荐的是采用Collections里面的关于线程同步的方法。 问题来源： 1.为什么要有HashMap？ 《Thinking In Java》里面有一个自己采用二维数组实现的保存key-value的demo，书上也说到性能问题，因为从数据结构的顺序结构的观点来看，常规的线性存储，你弱需要找到其中的某个元素，需要遍历这个链表或者数组，而遍历的同时需要让链表中的每一个元素都和目标元素做比较，相等才返回，Java里面用equals或者==。这对性能是毁灭性的伤害。 2.HashMap的优势是什么？ Hash算法是根据某个算法将一系列目标对象转换成地址，当要获取某个元素的时候，只需要将目标对象做相应的运算获得地址，直接获取。 3.Java中的Hash？ 事实上Java的数据无非三种，基本类型，引用类型(类似C里面的指针类型）和数组，有些地方说是2种类型，只有引用类型和数组。通过这三种数据类型可以构建出任何数据结构。在Java中，ArrayList这种底层是用Objec数组来构建的，而HashMap也是用数组来构建，只不过数据数组的数据类型是一个叫做Entry的内部类来保存key、value、hash(不是hashCode)和next(也是链表的下一个元素)。其实HashSet也是HashMap，只不过比较特殊，没有使用Entry的value而只用了key而已。看看HashSet的构造方法： public HashSet() { map = new HashMap<E，Object>(); } 所以从这个意义上来讲没必要讨论HashSet了，他只不过是特殊的HashMap而已。 HashMap详解： 基调：由于通过hash算法产生的逻辑地址可能导致冲突，所以对于一个长度为length的数组，里面存放小于length个数据元素的时候有可能出现冲突的现象，因为比如说要在长度为16的数组中存放字符串(也是一个空的HashMap默认的长度)，每个字符串通过调用自身的hashCode()方法会得到该字符串的hashCode，然后通过HashMap的这两个方法会算出在数组中的位置，也是下面的 i。 int hash = hash(key.hashCode()); int i = indexFor(hash， table.length); 任意字符串的hashCode通过上面2个方法都会得到一个i，这个i是在数组中的位置，这里比较巧妙的设计是indexFor(hash，table.length)这个方法： static int indexFor(int h， int length) { return h & (length-1); } 这个方法里面的任意h与(length-1)做位运算之后得到的值始终都是在length之内的，也是在数组table之内，因为拿任意一个数来和另一个数来做与运算，结果肯定是小于等于较小的哪一个数，我以前第一次看到这比较震惊，为什么那些人能想出这么巧妙的计算在table中的位置的方法。与此同时，既然字符串调用hashCode()会得到一个值，那么会出现不相同的字符串调用hashCode方法之后得到的值是一样的，这种可能性是存在的，而且几乎肯定是存在的。这时候需要在数组的某个位置增加一个链表结构，用户存储相同的hashCode的字符串，而这个时候HashMap的size同样也会自增1，尽管这2个字符串只有一个存在于数组中。HashMap中的size变量有两个作用，第一是通过调用size()方法来返回map的长度， public int size() { return size; } 第二个作用相当重要，是解决hash算法的核心力量，解决冲突。在HashMap的构造方法中可以看出，hashmap的长度和底层数组table都是capacity，但是还有一个变量叫做threshold，极限值，阈值的意思，默认情况的构造方法： public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
这个阈值是数组长度和加载因子的乘积，这东西有什么用呢，假设都按照默认情况来看，默认构造方法构造出来的hashmap长度为16，底层数组长度也为16，而阈值 threshold长度为12，因为默认加载因子是0.75。也是说当箱map中存放12个元素是，map的结构没什么变化，但是当存储第13个的时候，table需要扩容了，扩大为原来的2倍。这时候是什么结局呢，如果加载因子是1，那么map中存放16个的时候他是不会扩容的，table.length = 16，而为0.75的时候存放16个数据的时候table.length = 32。那么同样是存放16个数据，分别在长度为16的数组和32的数组中存放，出现冲突的几率一般来说16的数组要大一些，那为什么会大一些呢，因为某个数据存放进入数组的位置是根据 int hash = hash(key.hashCode()); int i = indexFor(hash， table.length); 这两个方法算出来的，其中包括table.length，换句话说，位置i跟hash和table.length是相关的，也是说位置i与table.length是联动的，换个角度，存放的16个数据假设是固定的，而得出hashCode的算法也是固定的，那么位置i只跟length的大小有关联了，一般来说length越大，数据的冲突几率低一些，在map.getValue(key)的时候需要在链表中比较的次数少一些，性能高一些。这是Java中hashmap的性能因素，一般来说加载因子factor大，同样个数的数据所占用空间越小，table.length越小，冲突几率越大，反之空间利用率低，性能高，类比一下，比如你地上放了10个碗，你手里面握了10颗大米，你撒下去，前提是必须10颗米都要撒进碗里，你是不是会发现有些碗里面装了两颗三颗，而有些碗是空的，接下来，你在地上摆20个碗，还是撒10颗米下去，依然是所有的米都要进碗，依然还是会出现有些晚是空的，有些是一颗两颗三颗这种现象，但是很明显一般来讲20个碗的时候每个碗里面装不止一颗的情况要比10个碗的情况要少，当然也不一定完全是这样，但是一般来说是这样，这是hash算法，如果设计的好的情况下我们希望每个碗里面都多放一颗进去，但是这种情况比较少见，但不管怎么说，按照普遍情况来看，20个碗的装多颗的情况是比10个碗装多颗的情况要少一点。从数据结构的角度来说叫做用空间换时间的策略，以空间换时间何止hash算法，双向链表也是用空间换时间的策略。至于说为什么默认是0.75，我估计这个是前辈们和科学家们总结出来的一个这种的办法，空间利用率比较不错的同时性能比较令人接受吧。 顺便说一下啊，当我们不断的往一个hashmap里面添加数据的时候，如果超过某个阈值，他会扩容，扩容的同时会让之前的所有元素重新生成地址，并且把原来的数组里面的数据迁移到新的数组中(新的数组容量是原来的两倍长度)。顺便说下，这个数据迁移其实对性能损耗还是相当大的，毕竟你是要复制数组，同时要重新构建每个元素的在table中的位置，因此我们可以在使用hashMap之前大概的估算一下这个hashMap里面大概会存多少个元素，这样可以在new hashmap的时候给定他的容量，这样数据迁移的次数相对少一些，性能更好一点。 接下来从JDK的源码来看看HashMap。 1.构造出一个空的HashMap。默认长度16，底层Entry数组也是16的默认长度。默认加载因子default_factor为0.75。阈值16*0.75=12。key和value都存在与Entry这个类型里面。 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } 2.调用put方法。
| public V put(K key， V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); 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; } } |
首先是判断key是否为空，如果为空，那么调用下面这个方法，这个方法说明，HashMap的null的key始终是存放在table的table[0]位置的，不管table[0]位置有没有冲突都是这样。
| 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; } |
如果不为空，那么继续，这里，如果算出来的位置i出已经有元素了，说明冲突了，那么遍历冲突链表，如果发现key相等，那么直接用新的value替换掉的value并且返回旧的value。这里只判断相等的情况而不判断不相等的情况，也是这里不做添加操作。
| int hash = hash(key.hashCode()); 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; } } |
接下来，上面的步骤说明，新添加的数据在位置i处不是key相等的情况，真正的添加数据了。调用addEntry(hash， key， value， i)方法。 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); } 此时把新的添加进table[i]位置，而原来的数据(可能是null也可能是一个链表)的引用直接存放进新的数据的next中。形成新的链表。 接下来是调用map的get(key)方法了。这个过程和put方法是逆向的。
| public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); 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.equals(k))) return e.value; } return null; } |
首先判断key == null， 如过为true，那么调用getForNullKey()方法。遍历table[0]出的链表，因为空key是存在table[0]处的。前面说到。 private V getForNullKey() { for (Entry<K，V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } 如果key == null 为false，那么上面get方法的下半部分，通过hashCode算出hash，通过hash和table.length算出位置i，遍历table[i]处的链表，ken相等，取出数据。
| int hash = hash(key.hashCode()); 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.equals(k))) return e.value; } return null; |
这里还有一个Java里面的规定，是2个对象的equals相等，那么hashCode也必须相等。但是hashCode相等equals不一定相等。这是hashmap存在于Java里面的依据，同时这是为什么会有冲突的原因了，两个不一样的对象计算出来的hashCode相等的原因。如果2个对象equals相等，但是hashcode不想等，那说明这2个元素都能存进hashmap，但是很明显hashmap里面的key是的，直接推翻了hashmap。 写得比较粗糙，HashMap里面的很多细节都没写，主要是因为一来我们只需要用HashMap行了，二来是细节源码里面都有，看一下知道了。
