jdk7 中HashMap的知识点总结
HashMap中的几个重要变量 默认初始容量,必须是2的n次方 static final int DEFAULT_INITIAL_CAPACITY = 16; 最大容量,当通过构造方法传入的容量比它还大时,就用这个最大容量,必须是2的n次方 static final int MAXIMUM_CAPACITY = 1 << 30; 默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 用来存储键值对,可以看到键值对都是存储在Entry中的 transient Entry<K,V>[] table; //capacity * load factor,超过这个数就会进行再哈希 int threshold; HashMap中的元素是用名为table的Entry数组来保存的,默认大小是16
jdk7中在面对key为String的时候采用了区别对待,会有alternative hashing,但是这个在jdk8中已经被删除了 存储结构 Entry是一个链表结构,不仅包含key和value,还有可以指向下一个的next 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; } ... put方法 public V put(K key,V value) { 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; } 首先通过hash方法对hashcode进行处理: final int hash(Object k) { int h = 0; h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 可以看到只是在key的hashcode值上做了一些处理,通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标: static int indexFor(int h,int length) { return h & (length-1); } 这个方法其实相当于对 当需要插入的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,0); return null; } putForNullKey方法只从 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,bucketIndex); } 可以看到jdk7中resize的条件已经发生改变了,只有当 void createEntry(int hash,int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash,e); size++; } 最后看createEntry,它先保存这个桶中的第一个Entry,创建新的Entry放入第一个位置,将原来的Entry接在后面。这里采用的是头插法插入元素。 get方法 其实get方法和put方法如出一辙,怎么放的怎么拿 public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } key为null时,还是去 private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } 否则调用getEntry方法: final Entry<K,V> getEntry(Object key) { 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; } 这个方法也是通过key的hashcode计算出它应该所在的下标,再遍历这个下标的Entry链,如果key的内存地址相等(即同一个引用)或者equals相等,则说明找到了 hash的原则 A、等幂性。不管执行多少次获取Hash值的操作,只要对象不变,那么Hash值是固定的。如果第一次取跟第N次取不一样,那就用起来很麻烦. B、对等性。若两个对象equal方法返回为true,则其hash值也应该是一样的。举例说明:若你将objA作为key存入HashMap中,然后new了一个objB。在你看来objB和objA是一个东西(因为他们equal),但是使用objB到hashMap中却取不出来东西。 C、互异性。若两个对象equal方法返回为false,hash值有可能相同,但最好是不同的,这个不是必须的,只是这样做会提高hash类操作的性能(碰撞几率低)。 解决hash碰撞的方法:
hashmap采用的就是链地址法,这种方法好处是无堆积现象,但是next指针会占用额外空间 和jdk8中的HashMap区别 在jdk8中,仍然会根据 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |