首页 > 代码库 > HashMap源码分析
HashMap源码分析
HashMap的数据结构是数组and链表。
一. HashMap继承自AbstractMap类,实现了Map接口。
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable
二. HashMap中定义的属性
1 // 默认初始容量必须是2的幂 2 static final int DEFAULT_INITIAL_CAPACITY = 16; 3 4 // 最大容量(2的30次方,传入容量过大将被这个值代替) 5 static final int MAXIMUM_CAPACITY = 1<<30; 6 7 // 默认装载因子 8 static final float DEFAULT_LOAD_FACTOR = 0.75f; 9 10 // 存储数据的Entry数组,长度为2的幂 11 transient Entry[] table; 12 13 // map中保存的键值对的数量 14 transient int size; 15 16 // 需要调整大小的极限值(容量*装载因子) 17 int threshold; 18 19 // 装载因子 20 final float loadFactor; 21 22 // map结构被改变的次数 23 transient volatile int modCount;
三. HashMap的构造方法
// 使用默认的容量及装载因子构造一个空的HashMap public HashMap(){ this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } // 根据给定的初始容量and装载因子创建一个空的HashMap // 初始容量小于0或装载因子小于等于0将报异常 public HashMap(int initialCapacity, float loadFactor){ if(initialCapacity<0) throw new IllegalArgumentException("Illegal initial capacity:"+initialCapacity); if(initialCapacity>MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if(loadFacor<=0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: "+loadFactor); int capacity = 1; while(capacity<initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int) (capacity * loadFactor); table = new Entry[capacity]; init(); } // 根据指定的容量创建一个空的HashMap public HashMap(int initialCapacity){ this(initialCapacity, DEFAULT_LOAD_FACOR); } // 通过传入的map创建一个HashMap,容器为默认容量16和(map.size()/DEFAULT_LOAD_FACTOR)+1的较大者,装载因子为默认值 public HashMap(Map<? extends K, ? extends V> m){ this(Math.max((int)(m.size()/DEFAULT_LOAD_FACTOR)+1, DEFAULT_INITIAL_CAPACITY),DEFAULT_LOAD_FACTOR); putAllForCreate(m); }
四. Map.Entry接口定义的方法
K getKey(); // 获取Key
V getValue(); // 获取Value
V setValue(); //设置Value
boolean equals(Object o); // 定义equals方法用于判断两个Entry是否相同
int hashCode();// 定义获取hashCode方法
五. HashMap.Entry类的具体实现
1 static class Entry<K,V> implements Map.Entry<K,V> { 2 final K key; 3 V value; 4 Entry<K,V> next; //对下一个节点的引用 5 final int hash;//哈希值 6 7 Entry(int h, K k, V v, Entry<K,V> n) { 8 value =http://www.mamicode.com/ v; 9 next = n; 10 key = k; 11 hash = h; 12 } 13 14 public final K getKey() { 15 return key; 16 } 17 18 public final V getValue() { 19 return value; 20 } 21 22 public final V setValue(V newValue) { 23 V oldValue =http://www.mamicode.com/ value; 24 value =http://www.mamicode.com/ newValue; 25 return oldValue; //返回的是之前的Value 26 } 27 28 public final boolean equals(Object o) { 29 if (!(o instanceof Map.Entry)) //先判断类型是否一致 30 return false; 31 Map.Entry e = (Map.Entry)o; 32 Object k1 = getKey(); 33 Object k2 = e.getKey(); 34 // Key相等且Value相等则两个Entry相等 35 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 36 Object v1 = getValue(); 37 Object v2 = e.getValue(); 38 if (v1 == v2 || (v1 != null && v1.equals(v2))) 39 return true; 40 } 41 return false; 42 } 43 // hashCode是Key的hashCode和Value的hashCode的异或的结果 44 public final int hashCode() { 45 return (key==null ? 0 : key.hashCode()) ^ 46 (value=http://www.mamicode.com/=null ? 0 : value.hashCode()); 47 } 48 // 重写toString方法,是输出更清晰 49 public final String toString() { 50 return getKey() + "=" + getValue(); 51 } 52 53 /** 54 *当调用put(k,v)方法存入键值对时,如果k已经存在,则该方法被调用(为什么没有内容?) 55 */ 56 void recordAccess(HashMap<K,V> m) { 57 } 58 59 /** 60 * 当Entry被从HashMap中移除时被调用(为什么没有内容?) 61 */ 62 void recordRemoval(HashMap<K,V> m) { 63 } 64 }
六. 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); // 下标
// 得到索引后,探测table[i]所在的链表,若发现key与传入的key相同,则替换并返回oldValue;若找不到,则通过
addEntry(hash, key, value, i)添加新的对象。
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()方法:该方法的主要作用是,防止质量较差的哈希函数带来过多的冲突问题。Java中int值占4个字节,即32位。根据这32位值进行移位、异或运算得到一个值。
static int hash(int h){ h ^= (h>>>20)^(h>>>12); return h^(h>>>7)^(h>>>4); }
indexFor()方法:返回hash值和table数组长度减1的与运算。为什么-1:这样可以保证结果的最大值为length-1,不会产生数组越界的问题。
static int indexFor(int h, int length) { return h & (length-1); }
七. get()方法
1 public V get(Object key){ 2 if(key==null) 3 return getForNullKey(); 4 int hash = hash(key.hashCode()); 5 for(Entry<K, V> e = table[indexFor(hash, table.length)]; e!=null; e=e.next){ 6 Object k; 7 if(e.hash==hash && ((k==e.key)==key || key.equals(k))) 8 return e.value; 9 } 10 return null; 11 }
getForNullKey()方法:这是一个私有方法,只有在get中被调用。该方法判断table[0]中的链表是否包含key为null的元素,包含则返回value,否则返回null。为什么遍历table[0]的链表?因为key为null时获得的hash值为0。
1 private V getForNullKey() { 2 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 3 if (e.key == null) 4 return e.value; 5 } 6 return null; 7 }
HashMap源码分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。