HashMap源码解析(jdk1.7)

深藏阁楼爱情的钟 2022-03-18 03:22 275阅读 0赞

### HashMap源码解析 ###

*  初始化信息
 *  添加元素
 *  删除元素
 *  查找元素
 *  containsKey：指定的key是否在HashMap中
 *  containsValue：查找HashMap中是否有指定的value
 *  isEmpty
 *  indexFor：返回h在table数组中的位置
 *  写在后面

# 初始化信息 #

//HashMap的初始容量，必须是2的n次幂
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
        //HashMap的最大容量，必须是2的n次幂
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        //加载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //存储数据的Entry数组，每一个entry是一个链表
        static final Entry<?,?>[] EMPTY_TABLE = { };
    
        /** * The table, resized as necessary. Length MUST Always be a power of two. * 这个entry数组，随着需要改变大小，长度必须是2的n次幂 */
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
        //HashMap中元素的总个数
        transient int size;
    
        /** * The next size value at which to resize (capacity * load factor). * HashMap的阈值，用于判断是否需要调整HashMap的大小，threshold = capacity * load factor * 初始大小 = 16 * 0.75 = 12 */
        // If table == EMPTY_TABLE then this is the initial capacity at which the
        // table will be created when inflated.
        int threshold;
    
        //加载因子实际大小
        final float loadFactor;
    
        //HashMap被改变的次数
        transient int modCount;
    
        //HashMap的默认阈值
        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

# 添加元素 #

public V put(K key, V value) { 
            if (table == EMPTY_TABLE) { 
                inflateTable(threshold);
            }
      		
            if (key == null)//如果key为null,则将此value放到table[0]中的链表上
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);//计算放到哪个桶上
            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);//如果没有重复的key，将当前元素放到table[i]的桶上
            return null;
        }
    
     private V putForNullKey(V value) { 
            for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
                if (e.key == null) { 
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
    
     void addEntry(int hash, K key, V value, int bucketIndex) { 
       /** * 判断当前的数组大小和阈值的关系，如果当前阈值≤数组大小且table[bucketIndex]不为null， * 就扩容，然后重新计算当前元素的位置 */
            if ((size >= threshold) && (null != table[bucketIndex])) { 
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);//重新计算桶的位置，因为桶的位置和桶的长度有关
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    
    
     void createEntry(int hash, K key, V value, int bucketIndex) { 
            Entry<K,V> e = table[bucketIndex];//先保存table[bucketIndex]的元素到e
            table[bucketIndex] = new Entry<>(hash, key, value, e);//然后将e设置为新元素的下一个节点，新元素为该链表的头结点
            size++;
       
       
       //entry的构造方法如下
       Entry(int h, K k, V v, Entry<K,V> n) { 
                value = v;
                next = n;
                key = k;
                hash = h;
        }
       
     }
    
    
     void resize(int newCapacity) { 
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) { 
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));//将元素从移动到newTable中
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新调整阈值
      }
    
       /** * Transfers all entries from current table to newTable. */
        void transfer(Entry[] newTable, boolean rehash) { 
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) { 
                while(null != e) { 
                    Entry<K,V> next = e.next;
                    if (rehash) { 
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

# 删除元素 #

public V remove(Object key) { 
            Entry<K,V> e = removeEntryForKey(key);
            return (e == null ? null : e.value);
    }
    
    final Entry<K,V> removeEntryForKey(Object key) { 
            if (size == 0) { //如果没有元素，返回null
                return null;
            }
            int hash = (key == null) ? 0 : hash(key);
            int i = indexFor(hash, table.length);
            Entry<K,V> prev = table[i];
            Entry<K,V> e = prev;
    
            while (e != null) { 
                Entry<K,V> next = e.next;
                Object k;
                //查找到元素，删除单链表的节点
                //只需将当前元素的前一个节点的下一个节点指向下下一个节点即可，即prev.next = next.next
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) { 
                    modCount++;
                    size--;
                    if (prev == e)//如果相等，表示删除的是第一个元素，所以要把table[i]指向next
                        table[i] = next;
                    else
                        prev.next = next;
                    e.recordRemoval(this);
                    return e;
                }
                prev = e;
                e = next;
            }
            return e;//如果这个桶没有元素，返回null
        }

# 查找元素 #

public V get(Object key) { 
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
        }
    
       final Entry<K,V> getEntry(Object key) { 
            if (size == 0) { 
                return null;
            }
    
            int hash = (key == null) ? 0 : hash(key);
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) { 
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }

# containsKey：指定的key是否在HashMap中 #

public boolean containsKey(Object key) { 
            return getEntry(key) != null;
      }
    
        final Entry<K,V> getEntry(Object key) { 
            if (size == 0) { 
                return null;
            }
    
            int hash = (key == null) ? 0 : hash(key);
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) { 
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }

# containsValue：查找HashMap中是否有指定的value #

public boolean containsValue(Object value) { 
            if (value == null)
                return containsNullValue();
    
            Entry[] tab = table;
            for (int i = 0; i < tab.length ; i++)
                for (Entry e = tab[i] ; e != null ; e = e.next)
                    if (value.equals(e.value))
                        return true;
            return false;
        }
    
    private boolean containsNullValue() { 
            Entry[] tab = table;
            for (int i = 0; i < tab.length ; i++)
                for (Entry e = tab[i] ; e != null ; e = e.next)
                    if (e.value == null)
                        return true;
            return false;
        }

# isEmpty #

public boolean isEmpty() { 
            return size == 0;
     }

# indexFor：返回h在table数组中的位置 #

/** * Returns index for hash code h.这里用&运算代替了取模运算，加快了速度，因为HashMap中的长度都是按照2的幂增长的，所以，length - 1 换算成二进制就是1111111。。。；所以h&(length-1)和h%length在数值上时一致的，但是速度更快。 */
    static int indexFor(int h, int length) { 
      return h & (length-1);
    }

# 写在后面 #

异或运算（^）

//异或运算，转换为二进制，相同为0，不同为1
    System.out.println(1^1);//0
    System.out.println(1^0);//1

三目运算符

//三目运算符从左往右运算
    int i = 1 > 0 ? 2 : 3 > 0 ? 7 : 8;
    int j = 1 < 0 ? 2 : 3 > 0 ? 7 : 8;
    
    System.out.println(i);//2
    System.out.println(j);//7

hashcode值

> 同一个对象的hash值一定相同，同一个字符串的hash值一定相同；反之不一定。
> 
> 两个对象相等，则hash值一定相同；反之不一定。