• 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
• 线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
• 二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

public class HashMap
     
       extends AbstractMap
      
        implements Map
       
        , Cloneable, Serializable{    //字段属性    //默认 HashMap 集合初始容量为16（必须是 2 的倍数）     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16     //集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数     static final int MAXIMUM_CAPACITY = 1 << 30;     //默认的填充因子     static final float DEFAULT_LOAD_FACTOR = 0.75f;     //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)     static final int TREEIFY_THRESHOLD = 8;     //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)     static final int UNTREEIFY_THRESHOLD = 6;     /**(JDK1.8新增) * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容， * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD */      static final int MIN_TREEIFY_CAPACITY = 64;    //初始化使用，长度总是 2的幂     transient Node
        
         [] table;     //保存缓存的entrySet（）     transient Set
         
          
           > entrySet; //此映射中包含的键值映射的数量。（集合存储键值对的数量） transient int size; /*** 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数 * 主要用于迭代器中的快速失败 */ transient int modCount; //调整大小的下一个大小值（容量*加载因子）。capacity * load factor int threshold; //散列表的加载因子。 final float loadFactor; //构造方法 /*** 默认构造函数，初始化加载因子loadFactor = 0.75 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } /**** @param initialCapacity 指定初始化容量 * @param loadFactor 加载因子 0.75 */ public HashMap(int initialCapacity, float loadFactor) { //初始化容量不能小于 0 ，否则抛出异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果初始化容量大于2的30次方，则初始化容量都为2的30次方 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //如果加载因子小于0，或者加载因子是一个非数值，抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //tableSizeFor()的主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2 的4次方16. this.threshold = tableSizeFor(initialCapacity); } // 返回大于等于initialCapacity的最小的二次幂数值。 // >>> 操作符表示无符号右移，高位取0。 // | 按位或运算 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } //添加元素 //hash(key)获取Key的哈希值，equls返回为true,则两者的hashcode一定相等，意即相等的对象必须具 有相等的哈希码。 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /**** @param hash Key的哈希值 * @param key 键 * @param value 值 * @param onlyIfAbsent true 表示不要更改现有值 * @param evict false表示table处于创建模式 * @return */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node
           
            [] tab; Node
            
              p; int n, i; //如果table为null或者长度为0，则进行初始化 //resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面 会详细讲解该方法 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //(n - 1) & hash：确保索引在数组范围内,相当于hash % n 的值 //通过 key 的 hash code 计算其在数组中的索引：为什么不直接用 hash 对 数组长度取模？因 为除法运算效率低 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //tab[i] 为null，直接将新的key- value插入到计算的索引i位置 else { //tab[i] 不为null，表示该位置已经有值了 Node
             
               e; K k; //e节点表示已经存在Key的节点，需要覆盖value的节点 //table[i]的首个元素是否和key一样,如果相同直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //节点key已经有值了，将第一个节点赋值给e //该链是红黑树 else if (p instanceof TreeNode) e = ((TreeNode
              
               )p).putTreeVal(this, tab, hash, key, value); //该链是链表 else { //遍历链表 for (int binCount = 0; ; ++binCount) { //先将e指向下一个节点，然后判断e是否是链表中最后一个节点 if ((e = p.next) == null) { //创建一个新节点加在链表结尾 p.next = newNode(hash, key, value, null); //链表长度大于8，转换成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //key已经存在直接终止，此时e的值已经为 p.next if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //修改已经存在Key的节点的value e.value = value; afterNodeAccess(e); //返回key的原始值 return oldValue; } } ++modCount; //用作修改和新增快速失败 if (++size > threshold) //超过最大容量，进行扩容 resize(); afterNodeInsertion(evict); return null; } //获取元素 public V get(Object key) { // 若key为null，遍历table[0]处的链表（实际上要么没有元素，要么只有一个Entry对象），取出 key为null的value if (key == null) return getForNullKey(); // 若key不为null，用key获取Entry对象 Entry
               
                 entry = getEntry(key); // 若链表中找到的Entry不为null，返回该Entry中的value return null == entry ? null : entry.getValue(); } final Entry
                
                  getEntry(Object key) { if (size == 0) { return null; } // 计算key的hash值 int hash = (key == null) ? 0 : hash(key); // 计算key在数组中对应位置，遍历该位置的链表 for (Entry
                 
                   e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; // 若key完全相同，返回链表中对应的Entry对象 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } // 链表中没找到对应的key，返回null return null; } //扩容 final Node
                  
                   [] resize() { //将原始数组数据缓存起来 Node
                   
                    [] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; //原数组如果为null，则长度赋值 0 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //如果原数组长度大于0 if (oldCap >= MAXIMUM_CAPACITY) { //数组大小如果已经大于等于最大值(2^30) threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就 不会扩容了 return oldTab; } //原数组长度扩大1倍(此时将原数组扩大一倍后的值赋给newCap)也小于2^30次方，并且原数组 长度大于等于初始化长度16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold // 阀值扩大1倍 //如果原数组长度扩大一倍后大于MAXIMUM_CAPACITY后，newThr还是0 }else if (oldThr > 0) // initial capacity was placed in threshold //旧容量为0，旧阀值大于0，则将新容量直接等于就阀值 //在第一次带参数初始化时候会有这种情况 //newThr在面算 newCap = oldThr; else { // zero initial threshold signifies using defaults //阀值等于0，oldCap也等于0（集合未进行初始化） //在默认无参数初始化会有这种情况 newCap = DEFAULT_INITIAL_CAPACITY; //数组长度初始化为16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //阀值等于 16*0.75=12 } //计算新的阀值上限 //此时就是上面原数组长度扩大一倍后大于MAXIMUM_CAPACITY和旧容量为0、旧阀值大于0的情况 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //将阀值上限设置为新阀值上限 threshold = newThr; //用于抑制编译器产生警告信息 @SuppressWarnings({"rawtypes","unchecked"}) //创建容器大小为newCap的新数组 Node
                    
                     [] newTab = (Node
                     
                      [])new Node[newCap]; //将新数组赋给table table = newTab; //如果是第一次,扩容的时候,也就是原来没有元素,下面的代码不会运行,如果原来有元素,则要将原来 的元素,进行放到新扩容的里面 if (oldTab != null) { //把每个bucket都移动到新的buckets中 for (int j = 0; j < oldCap; ++j) { Node
                      
                        e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //元数据j位置置为null，便于垃圾回收 if (e.next == null) //数组没有下一个引用（不是链表） //直接将e的key的hash与新容量重新计算下标,新下标的元素为e newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //红黑树 ((TreeNode
                       
                        )e).split(this, newTab, j, oldCap); else { // preserve order Node
                        
                          loHead = null, loTail = null; Node
                         
                           hiHead = null, hiTail = null; Node
                          
                            next; do { next = e.next; //原索引 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //原索引放到bucket里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //原索引+oldCap放到bucket里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } return newTab; }}
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

static class Entry
     
       implements Map.Entry
      
        {     final K key; V value;     /** 指向下一个元素的引用 */     Entry
       
         next;     int hash;     /*** 构造方法为Entry赋值 */     Entry(int h, K k, V v, Entry
        
          n) {         value = v;         next = n;        key = k;         hash = h;     }}
        
       
      
     

1. 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失(因为头插法插入数据)。
2. 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。