JDK源代码分析聚集篇-------HashMap(一队不够快，多排几队就是)

作者：手浪用户2602890531 | 来源：互联网 | 2023-01-02 12:11

众所周知，Map是用来存储键值对的数据的，而且他的好处就是根据键值能够快速定位，技能保持这ArrayList的优势，又能够保持LinkedList的容易删除和增加的优势，那么我们来分析分析他的实

众所周知，Map是用来存储键值对的数据的，而且他的好处就是根据键值能够快速定位，技能保持这ArrayList的优势，又能够保持LinkedList的容易删除和增加的优势，那么我们来分析分析他的实现机理，老规矩，先给出类图：

首先先来分析一下HashMap

static final int DEFAULT_INITIAL_CAPACITY = 16;

最大容量2的15次方+1；
static final int MAXIMUM_CAPACITY = 1 <<30;

默认加载因子：
static final float DEFAULT_LOAD_FACTOR = 0.75f;

内部实现的机制是用具有键值对格式的单个的entry数组实现：

 
  transient Entry[] table;
   static class Entry implements Map.Entry {
        final K key; //键
        V value;    // 值
        Entry next;  //下一个
        final int hash;   //哈西值
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        public final K getKey() {
            return key;
        }
        public final V getValue() {
            return value;
        }
        public final V setValue(V newValue) {
        V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }
        public final String toString() {
            return getKey() + "=" + getValue();
        }
        void recordAccess(HashMap m) {
        }
        void recordRemoval(HashMap m) {
        }
    }
 
 

当前的数组大小：
transient int size;

构造函数初始化：
设置初始化的容积和加载因子

 
  public HashMap(int initialCapacity, float loadFactor) {
        //初始化容积必须大于0
        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);
        //找出一个数的平方大于当前给出的初始化容积，比如是初始化是10的话，那么最终的容积就是16
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        //用容积来初始化数组大小；size当前还是为0；
        table = new Entry[capacity];
        //初始化动作，可以留给子类实现，模板模式的应用
        init();
    }
 
 

这是一个hashcode的转换算法；他能够把对象的hashcode转换成为小于length-1的整数作为数组的下标；那么势必会出现重合

 
      static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
 
 

我们先看增加方法：

 
   public V put(K key, V value) {
        //判断键值是否为空；
        if (key == null)
            return putForNullKey(value);
        
        //得到hashcode
        int hash = hash(key.hashCode());
        //得到一个小于数组长度（取的是与操作）的下标
        int i = indexFor(hash, table.length);
        //在数组中找到该下标的entry值；
        //事实上entry也是一个链表，相对于LinkedList来说，他的entry是单向的
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            //如果存在键值是同一对象的entry,那么用新值覆盖旧值，不存在则再往下找，知道末尾
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //增加修改次数
        modCount++;
        //增加这个entry到该下标列表的首部
        addEntry(hash, key, value, i);
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];
        //可见是放在該下标链表的第一位的
        table[bucketIndex] = new Entry(hash, key, value, e);
        //在这里增加了size;
        if (size++ >= threshold)
            resize(2 * table.length);
    }
 
 

如果key是null的话：
那么他可以不用通过hashcode定位数组中的队列下标-_-||事实上他也没有hashcode；规定在0位存放这个链表的头；可见在HashMap中是可以

存放null的key的；但是正因为其没有hashcode那么就只能存放一个元素，而不是像其他一样能存放多个；但是另外我们可见，你可以考虑把使

用的最多的值的键设置成为null，因为他是找到的最快的；

 
  
private V putForNullKey(V value) {
        for (Entry 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;
    }
 
 

上面说了存放了，下面我们再来看看如何取出来把：

 
  final Entry getEntry(Object key) {
        //经过算法得到这个key对应的hashcode，可见hashcode是固定的对应，而不是随机的；如果是null的话为0，经过与操作还是0，直接 
       //定位到table[0]否则查找出下标
       int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
     //匹配这个key的hashcode和数值，可见不是同一的值其hashcode是可能一样的，否则如果是一一对应则没必要匹配key了
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        } 
    //没有找到，为空；
       return null;
 
 

我们再来看看其容量是如何增长的：

 
      public void putAll(Map m) {
        //得到新增加进来的元素的个数
        int numKeysToBeAdded = m.size();
        if (numKeysToBeAdded == 0)
            return;
         //如果新增加的元素个数大于原来容积*加载因子；可见我们必须要扩充容量了
        if (numKeysToBeAdded > threshold) {
            //那么我们增加的容量将是该新增元素个数+预留空间的总数
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
            if (targetCapacity > MAXIMUM_CAPACITY)
                targetCapacity = MAXIMUM_CAPACITY;
            int newCapacity = table.length;
            //如果我们现在的表的容量小于新增加的容量，那么我们扩展两倍，如果还小，再扩大两倍，直到他的大于当前需要的容量
            while (newCapacity < targetCapacity)
                newCapacity <<= 1;
            if (newCapacity > table.length)
                resize(newCapacity);
        }
        
        //添置新的"家具"
        for (Iterator> i = m.entrySet().iterator(); i.hasNext(); ) {
            Map.Entry e = i.next();
            put(e.getKey(), e.getValue());
        }
    }
 
 

用新的容积开辟了一块足够大的存储空间，

 
  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);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
并且把家具从以前的“小房子”帮到了“大房子”
 void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            //得到各个数组元素的链表的头
            Entry e = src[j];
            if (e != null) {
                src[j] = null; //一定要把原来的“小房子”收拾好，方便垃圾回收；
                do {
                    Entry next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
 
 

新增，查找，都看过了，我们来看一下删除：

 
  public V remove(Object key) {
        Entry e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
  
    final Entry removeEntryForKey(Object key) {
        //定位查找到链表表头；
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry prev = table[i];
        Entry e = prev;
        while (e != null) {
            Entry next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                //若能找到，修改前后的链表节点的指向，从中删除；
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            //方便链表往下传递；保存prev是因为是单向链表，所以一旦找到的目标节点，无法通过该节点得到钱一个节点，就无法更改前
一个节点的指//向，所以要保存prev
            prev = e;
            e = next;
        }
        return e;
    }
 
 

现在我们再看一下如何单独取到他的键值集合或者值集合:

 
  values实现了一个内部私有类；
  public Collection values() {
        Collection vs = values;
        return (vs != null ? vs : (values = new Values()));
    }
//AbstractCollection 把一些基本的curd委托给了iteartor，所以只需重载其获取iteartor的方法；
    private final class Values extends AbstractCollection {
        
        //重载了iteartor
        public Iterator iterator() {
            return newValueIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsValue(o);
        }
        public void clear() {
            HashMap.this.clear();
        }
    }
下面是该iteartor的获取：其中主要的是看看我们获取的value的collection是如何排序的；
    private abstract class HashIterator implements Iterator {
        Entry next;    // next entry to return
        int expectedModCount;   // For fast-fail
        int index;      // current slot
        Entry current; // current entry
        HashIterator() {
            expectedModCount = modCount;
            //如果该HashMap有元素
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                然后把next和index都调至该table数组的链表头中不为空的地方；
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        public final boolean hasNext() {
            return next != null;
        }
        final Entry nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry e = next;
            if (e == null)
                throw new NoSuchElementException();
            //代表这个链表遍历完成了，需要开始遍历下一个table下标的链表了
            if ((next = e.next) == null) {
                Entry[] t = table;
            //找到下一个不为空的table元素
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        current = e;
            return e;
        }
        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }
ValueIterator ：
 private final class ValueIterator extends HashIterator {
        public V next() {
            return nextEntry().value;
        }
    }
 
 

这是我们会问加入我在这个value的collection中增加元素会出现什么样的情况呢，次序会不会打乱，对不起，AbstractCollection不存在add

的，iteartor也是不允许增加元素的；

对于来说keySet来说是同理的，不过因为key是不存在一样的，所以，我们不会返回collection而返回set,避免了重复key的出现；

好，我们今天先把HashMap分析完成；

推荐阅读

import
关于LinkedHashMap实现LRU缓存算法

缓存这个东西就是为了提高运行速度的，由于缓存是在寸土寸金的内存里面，不是在硬盘里面，所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List：每 ... [详细]

蜡笔小新 2023-09-10 10:48:58
hashtable
java1.7集合源码赏析系列：HashTable、ConcurrentHashMap、HashMap差异分析

HashTable与ConcurrentHashMap均可实现HashMap的功能，对外提供了键值对存储的数据结构。但是在内部结构及实现上有何区别，性能上的差异到底在哪里又是如何导致的 ... [详细]

蜡笔小新 2023-09-14 08:45:47
post
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
default
Java容器中的compareto方法排序原理解析

本文从源码解析Java容器中的compareto方法的排序原理，讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点，回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录，展示了整个讲解过程。 ... [详细]

蜡笔小新 2023-12-14 13:53:31
import
Java中vector的使用详解

本文详细介绍了Java中vector的使用方法和相关知识，包括vector类的功能、构造方法和使用注意事项。通过使用vector类，可以方便地实现动态数组的功能，并且可以随意插入不同类型的对象，进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下，使用vector类是一个很好的选择。 ... [详细]

蜡笔小新 2023-12-13 14:14:39
default
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新 2023-12-13 08:44:30
default
广度优先遍历（BFS）算法的概述、代码实现和应用

本文介绍了广度优先遍历（BFS）算法的概述、邻接矩阵和邻接表的代码实现，并讨论了BFS在求解最短路径或最短步数问题上的应用。以LeetCode中的934.最短的桥为例，详细阐述了BFS的具体思路和代码实现。最后，推荐了一些相关的BFS算法题目供大家练习。 ... [详细]

蜡笔小新 2023-12-09 02:51:05
js
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
js
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
js
猜字母游戏

猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]

蜡笔小新 2023-12-13 12:04:03
import
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
default
iOS数据库Sqlite的SQL语句分类和常见约束关键字

本文介绍了iOS数据库Sqlite的SQL语句分类和常见约束关键字。SQL语句分为DDL、DML和DQL三种类型，其中DDL语句用于定义、删除和修改数据表，关键字包括create、drop和alter。常见约束关键字包括if not exists、if exists、primary key、autoincrement、not null和default。此外，还介绍了常见的数据库数据类型，包括integer、text和real。 ... [详细]

蜡笔小新 2023-12-12 18:42:03
default
深入理解Kafka服务端请求队列中请求的处理

本文深入分析了Kafka服务端请求队列中请求的处理过程，详细介绍了请求的封装和放入请求队列的过程，以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析，帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]

蜡笔小新 2023-12-12 16:14:59
default
重入锁（ReentrantLock）学习及实现原理

本文介绍了重入锁（ReentrantLock）的学习及实现原理。在学习synchronized的基础上，重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理，并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式，通过对比和分析，读者可以更好地理解和应用重入锁。 ... [详细]

蜡笔小新 2023-12-11 15:16:28
default
STL迭代器的种类及其功能介绍

本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系，并详细描述了各个迭代器的功能和使用方法。其中，输入迭代器用于从容器中读取元素，输出迭代器用于向容器中写入元素，正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]

蜡笔小新 2023-12-10 15:17:25

手浪用户2602890531

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章