java之HashMap

青旅半醒 2024-04-19 10:12 49阅读 0赞

### 文章目录 ###

*   *   *  一、底层数据结构
         *  二、常用方法思维导图
         *  三、部分源代码
         *   *  1. put
             *  2. get
             *  3. containsValue
             *  4. values
             *  5. entrySet
             *  6. keySet
         *  三、遍历集合
         *  四、总结

### 一、底层数据结构 ###

`transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;`

**HashMap是基于数组+链表实现**, 数组类型为**Entry<K,V>**.

### 二、常用方法思维导图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]

### 三、部分源代码 ###

#### 1. put ####

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {//表为空时初始化容量
                inflateTable(threshold);
            }
            if (key == null) // key为null
                return putForNullKey(value);
            int hash = hash(key); // 计算key的hash值
            int i = indexFor(hash, table.length); // 根据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); //添加元素至table
            return null;
        }

添加元素的大致思路:  
**1.计算元素在table中的索引index.**  
**2.创建Entry对象**  
**3.table\[index\] = Entry**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 1]  
这样就涉及到2个问题:  
1.**索引重复**  
2.**数组扩容**  
  
  
索引重复

//举个栗子
    Map<String, String> map = new HashMap<>()
    map.put("yk", "1111"); //index=13
    map.put("ah", "1111"); // index=13

当执行`map.put("yk", "1111")`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 2]  
当执行`map.put("ah", "1111");`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 3]  
**更新当前索引指向新的对象, 将新对象的`Entry<K,V> next`属性指向原来的对象.** 这样看来, HashMap是于一种**数组+链表**的结构.  
  
  
数组扩容

1.扩容在何时发生?

(1).第一次添加元素时

// Find a power of 2 >= toSize
            int capacity = roundUpToPowerOf2(toSize);
    
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity)

**当容量不等于 2 n 2^n 2n时**, `roundUpToPowerOf2(toSize)`方法会根据初始化容量(capacity)得到一个大于容量(>capacity)的值, 该值等于 2 n 2^n 2n

(2). 当元素数量大于一个临界值 && null != table\[bucketIndex\]

if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length); //容量会扩充为原来的2倍
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);

`threshold`表示当元素数量(size)达到这个值时, 可能会进行扩容. 在通常情况下`capacity > threshold`, 因此即使  
`size >= threshold`, table中可能还有空余位置, 因此需要另一个条件的支持`null != table[bucketIndex]`.

2. 如何扩容?

1.创建新的table

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]; //重新创建table
            transfer(newTable, initHashSeedAsNeeded(newCapacity));//将元素进行迁移
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

2.将索引处的值迁至新的table

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;
                }
            }
        }

#### 2. get ####

table中**每一个元素都是Entry<K,V>的实例.** 只要计算出索引, 便能拿到该索引处指向的实例, 然后返回value属性的值。  
这与List的`get(int i)`有相似之处, 都可以根据索引访问数据。不同的是当我们调用List的方法时并不知道该处索引代表什么意思, 例如`get(0)`

public V get(Object key) {
          if (key == null)
               return getForNullKey();
           Entry<K,V> entry = getEntry(key); //根据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;
        }

#### 3. containsValue ####

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;
        }

它的思路就是:遍历整个table, 然后比较value.不好的地方在于执行的速度与表的长度有关。

#### 4. values ####

public Collection<V> values() {
            Collection<V> vs = values;
            return (vs != null ? vs : (values = new Values()));
        }

返回value的集合。

#### 5. entrySet ####

public Set<Map.Entry<K,V>> entrySet() {
            return entrySet0();
        }

该方法返回一个Set集合, 存放map集合所有的元素(Entry类型).不应该将key-value分别看待, 每一个映射就代表一个Entry实例.获取该Set之后就可以通过Iterator或for-each来遍历.

#### 6. keySet ####

public Set<K> keySet() {
            Set<K> ks = keySet;
            return (ks != null ? ks : (keySet = new KeySet()));
        }

该方法返回key的集合.

### 三、遍历集合 ###

1.**获取key的集合, 根据key遍历**

// 添加元素
    Map<String, String> map = new HashMap<>();
    map.put("1", "f");
    map.put("2", "a");
    map.put("3", "g");

for(String key : map.keySet()){
        System.out.println(key + " = " + map.get(key));
    }

2.**获取entry集合, 直接遍历**

for(Map.Entry<String, String> entry : map.entrySet()){
        System.out.println(entry);
     }

### 四、总结 ###

1.HashMap是一个**数组+链表**的结构. 因此既有数组**随机访问**的特性, 也有链表在**插入和删除**操作上的优势.但是相对普通的集合(ArrayList, LinkedList)要消耗更多的内存.

2.HashMap**根据key的hash值与表长度(table.length)** 计算存储位置. 因此在同一个索引处可能有多个元素.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190919090217212.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190917174709159.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190917174935778.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190917174834986.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy,size_16,color_FFFFFF,t_70