一、结构 HashMap的结构由数组和链表组成,可以说是一个链表类型的数组: 快速定位方式:key值得hash变换作为数组索引快速找到对应数组块,之后通过hash值对比从链表中查找到匹配项。 hash函数: hash()
key的hash值是实际是key的hashCode值的低16位与高16位异或结果。之所以这样是为了减少数组定位时发生哈希碰撞。 数组下标是这样确定的: i =(n-1)& hash //n=tab.length(),hash = hash(key)
从数组下标确定算法可以看出,实际参与运算的基本都是hash的低位,这样发生哈希冲突的可能性就比较高,所以hash函数中才会用hashcode值高低位取异或;
二、默认参数[url=][/url]
1 /** 2 * The default initial capacity - MUST be a power of two. 3 */ 4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 5 6 /** 7 * The maximum capacity, used if a higher value is implicitly specified 8 * by either of the constructors with arguments. 9 * MUST be a power of two <= 1<<30.10 */11 static final int MAXIMUM_CAPACITY = 1 << 30;12 13 /**14 * The load factor used when none specified in constructor.15 */16 static final float DEFAULT_LOAD_FACTOR = 0.75f;[url=][/url]
规定HashMap容量总为2的幂次方,最小16,最大2的30次方; DEFAULT_LOAD_FACTOR 默认的负载因子,参与通过无参构造的HashMap初始容量计算。 三、属性[url=][/url]
1 transient Node<K,V>[] table;2 transient Set<Map.Entry<K,V>> entrySet;3 transient int size;4 //容量阈值5 int threshold;6 //负载因子7 final float loadFactor;[url=][/url]
当通过无参构造函数初始化时,loadFactor = DEFAULT_LOAD_FACTOR。实际上通过无参构造HashMap时,初始容量为 = DEFAULT_INITIAL_CAPACITY * loadFactor(见方法rsize())。 四、构造函数hashMap有4个构造函数; 一个无参构造,初始容量和负载因子都取默认值; 一个通过已有Map构造; 两个自定义容量构造; jdk1.8的构造函数并没有初始化table,table初始化放在了第一次put中。
[url=][/url]
1 public HashMap(int initialCapacity, float loadFactor) { 2 if (initialCapacity < 0) 3 throw new IllegalArgumentException("Illegal initial capacity: " + 4 initialCapacity); 5 if (initialCapacity > MAXIMUM_CAPACITY) 6 initialCapacity = MAXIMUM_CAPACITY; 7 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 8 throw new IllegalArgumentException("Illegal load factor: " + 9 loadFactor);10 this.loadFactor = loadFactor;11 this.threshold = tableSizeFor(initialCapacity);12 }[url=][/url]
除了无参构造,都应用到一个方法tableSizeFor(); tableSizeFor
此算法计算出大于等于入参的最小2的幂次方,由于规定map容量必须为2的幂次方,所以经由此方法得出自定义的最佳容量。
|