HashMap数据结构是一个数组，下角标是通过hash值得到的，每个数组value是一个链表（即hash值相同）。HashMap查找是很快的，时间复杂度不是O（n），可以通过hash算法直接计算出来。
其中put源码：
public V put(K key, V value) { // 处理key为null，HashMap允许key和value为null if (key == null) return putForNullKey(value); // 得到key的哈希码 int hash = hash(key); // 通过哈希码计算出bucketIndex int i = indexFor(hash, table.length); // 取出bucketIndex位置上的元素，并循环单链表，判断key是否已存在 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不存在时，加入新元素 modCount++; addEntry(hash, key, value, i); return null; }由上可见，key和value都可以是null。
初始容量和加载因子
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 16;// 默认初始容量为16，必须为2的幂 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量为2的30次方 /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认加载因子0.75 /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry<K,V>[] table;// Entry数组，哈希表，长度必须为2的幂 /** * The number of key-value mappings contained in this map. */ transient int size;// 已存元素的个数 /** * The next size value at which to resize (capacity * load factor). * @serial */ int threshold;// 下次扩容的临界值，size>=threshold就会扩容 /** * The load factor for the hash table. * * @serial */ final float loadFactor;// 加载因子各种构造方法都会调用
public HashMap(int initialCapacity, float loadFactor) { // 参数判断，不合法抛出运行时异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity // 这里需要注意一下 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; // 设置加载因子 this.loadFactor = loadFactor; // 设置下次扩容临界值 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化哈希表 table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); } 通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。 加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点，可以想想为什么）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子(实际上就是最大条目数小于初始容量*加载因子)，则不会发生 rehash 操作。如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。 当HashMap存放的元素越来越多，到达临界值(阀值)threshold时，就要对Entry数组扩容，这是Java集合类框架最大的魅力，HashMap在扩容时，新数组的容量将是原来的2倍，由于容量发生变化，原有的每个元素需要重新计算bucketIndex，再存放到新数组中去，也就是所谓的rehash。HashMap默认初始容量16，加载因子0.75，也就是说最多能放16*0.75=12个元素，当put第13个时，HashMap将发生rehash，rehash的一系列处理比较影响性能，所以当我们需要向HashMap存放较多元素时，最好指定合适的初始容量和加载因子，否则HashMap默认只能存12个元素，将会发生多次rehash操作。
参考：https://blog.csdn.net/ghsau/article/details/16843543
