HashMap的存储原理

HashMap的存储原理

import java.util.HashMap;/** * * 创建对象HashMap map = new HashMap(); * * static final int DEFAULT_INITIAL_CAPACITY = 16; * static final float DEFAULT_LOAD_FACTOR = 0.75f; * public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); this(16,0.75f) } 默认哈希表主数组的长度是16，默认的加载因子是0.75f transient Entry[] table; public HashMap(int initialCapacity, float loadFactor) { //给装填因子赋值 0.75f this.loadFactor = loadFactor; // threshold = 16*0.75=12 门槛值 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //table就是主数组的引用，创建了一个主数组长度是16的哈希表 table = new Entry[capacity]; } * * 添加键值对map.put("cn", "China"); * * public V put(K key, V value) { cn China * //如果key是空，进行特殊的处理 if (key == null) return putForNullKey(value); //计算key的哈希码，进行了二次散列，目的为了保证不同key的哈希码尽量不同，更分散更高效 int hash = hash(key); //调用函数得到存储位置 int i = indexFor(hash, table.length); //将元素添加到指定的位置 for (Entry e = table[i]; e != null; e = e.next) { Object k; //找到了现在要添加到关键字 ，新value替换旧的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value;//America替换了the United States e.recordAccess(this); return oldValue; } } modCount++; //如果没有找到，就创建一个新的节点并加入到链表中 addEntry(hash, key, value, i); return null; } * * final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } 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); //采用位运算，效率更高结果等同于下一条语句 return h%length; h%16;//0--15 } void addEntry(int hash, K key, V value, int bucketIndex) { //如果达到了门槛值，就扩容 12>=12 if ((size >= threshold) && (null != table[bucketIndex])) { //一次扩容1倍 16 32 64 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //创建新的结点并加入 createEntry(hash, key, value, bucketIndex); } * 根据key获取值map.get("cn") * * * public V get(Object key) { * //如果关键字是null，特殊处理 if (key == null) return getForNullKey(); //根据key找到对应的Entry，Entry就是一个存储了key-value的哈希表的链表节点 Entry entry = getEntry(key); // return null == entry ? null : entry.getValue(); } * * 哈希表中一个链表节点的结构，[在JDK1.8中变成了Node] * static class Entry implements Map.Entry { final K key; V value; Entry next; int hash; } * * final Entry getEntry(Object key) { * //二次哈希，得到哈希码 int hash = (key == null) ? 0 : hash(key); //根据哈希码得到存储的位置 int i= indexFor(hash, table.length)； //在哈希表中查找指定key的Entry for (Entry e = table[i]; e != null; e = e.next) { Object k; //找到了就返回 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } //如果没有找到，返回null return null; } * @author Administrator * */public class TestHashMap { public static void main(String[] args) { HashMap map = new HashMap(); map.put("cn", "China"); map.put("us", "the United States"); map.put("us", "America"); System.out.println(map.get("cn")); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。