关于hashmap:java-hashmap

54次阅读

共计 50334 个字符,预计需要花费 126 分钟才能阅读完成。

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

## 手写 Java HashMap 外围源码
上一章手写 LinkedList 外围源码,本章咱们来手写 Java HashMap 的外围源码。
咱们来先理解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明确?没关系。咱们来具体解说一下 HashMap 的原理。

HashMap 应用剖析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));// 输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得,Object 类有一个 hashCode()办法,返回对象的 hashCode 值,能够了解为返回了对象的内存地址,暂且不论返回的是内存地址或者其它什么也好,先不论,至于 hashCode()办法回返的数是怎么算的?咱们也不论

第 1 咱们只须要记住:这个函数返回的是一个数就行了。
第 2 HashMap 外部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 寄存的?
上面咱们用一张图来演示

从上图能够看出:
注:上图中数组的大小是 7,是多少都行,只是咱们这里就画了 7 个元素,咱们就以数组大小为 7 来阐明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范畴是[0 , 6]
  2. 获得 key 也就是 ”name” 的 hashCode,这是一个数,不论这个数是多少,对 7 进行取余数,那么范畴必定是 [0 , 6],正好和数组的索引是一样的。
  3. “name”.hashCode() % 7 的值如果为 2,那么 value 也就是 ”tom” 应该寄存的地位就是 2
  4. data[2] = “tom” , 存到数组中。是不是很奇妙。

2 上面再来看看如何取?
也用一张图来演示底层原理,如下

由上图可知:

  1. 首先也是获取 key 也就是 ”name” 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,必定也是 2
  3. 从数组的第 2 个地位把 value 取出,即: String value = data[2]

注:有几点须要留神

  1. 某个对象的 hashCode()办法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数 , 范畴是 [0, n – 1]

注:有几个问题须要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好雷同了,也就是都映射在了数组的同一地位,怎么办?这就是 hash 抵触问题

比方 9 % 7 == 2,16 % 7 == 2都等于 2
答:数组中寄存的是一个节点的数据结构,节点有 next 属性,如果 hash 抵触了,单链表进行寄存,取的时候也是一样,遍历链表

  1. 如果数组曾经存满了怎么办?

答:和 ArrayList 一样,进行扩容,从新映射

  1. 间接应用 hashCode()值进行映射,产生 hash 抵触的概论很大,怎么办?

答:参考 JDK 中 HashMap 中的实现,有一个 hash()函数,再对 hashCode()的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的地位下面曾经有值了,那么就用链表寄存在以后的后面。数组 + 链表构造,是 HashMap 的底层构造
如果咱们的数组外面寄存的元素是 QEntry,如下图:

手写 HashMap 外围源码

下面剖析了原理,接下来咱们用起码的代码来提醒 HashMap 的原理。
咱们就叫 QHashMap 类,同时数组外面的元素须要也须要定义一个类,咱们定义在 QHashMap 类的外部。就叫 QEntry

QEntry 的定义如下:

    // 底层数组中寄存的元素类
   public static class QEntry<K, V> {
        K key;      // 寄存 key
        V value;    // 寄存 value
        int hash;   //key 对应的 hash 值
        
        //hash 抵触时,也就是映射的地位上曾经有一个元素了
        // 那么新加的元素作为链表头,曾经寄存的放在前面
        // 即保留在 next 中,一句话:增加新元素时,增加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,上面看下 QHashMap 类中须要哪些属性?
QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数据中元素的个数越多时,hash 抵触也容易产生
    // 所以,须要在数组还没有用完的状况下就开始扩容
    // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容
    // 比方数组的大小是 100,当外面的元素减少到 75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 寄存元素的数组
    private QEntry[] table;

    // 数组中元素的个数
    private int size;
 
    ......
}    

只须要两个常量和两个变量就够了。
上面咱们看下 QHashMap 的构造函数,为了简略,只实现一个默认的构造函数

  public QHashMap() {
        // 创立一个数组,默认大小为 16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        
        // 此时元素个数是 0
        size = 0;
    }

咱们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put()函数的实现如下:

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

正文很具体,这里有几个函数
hash() 函数是间接从 HashMap 源码中拷贝的,不必纠结这个算法。
indexFor(),传入 hash 和数组的大小,从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下:

   // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,咱们就开始扩容
resize()的源码如下:

  // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

相比 put()函数来说,get()就简略多了。
只须要通过 hash 值找到相应的数组的地位,再遍历链表,找到一个元素外面的 key 与传的 key 相等就行了。
put()办法的源码如下:

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
                
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

下面就是 QHashMap 的外围源码,咱们没有实现删除。
上面是把 QHashMap 整个类的源码收回来

QHashMap 残缺源码如下:

public class QHashMap<K, V> {
    // 默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 默认的扩容因子,当数组的大小大于或者等于以后容量 * 0.75 的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层用一个数组来存放数据
    private QEntry[] table;

    // 数组大小
    private int size;

    // 一个点节,数组中寄存的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 依据 key 获取 value
    public V get(K key) {

        // 同样为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 对 key 进行求 hash 值
        int hash = hash(key.hashCode());

        // 用 hash 值进行映射,失去应该去数组的哪个地位上取数据
        int index = indexFor(hash, table.length);

        // 把 index 地位的元素保留下来进行遍历
        // 因为 e 是一个链表,咱们要对链表进行遍历
        // 找到和 key 相等的那个 QEntry,并返回 value
        QEntry<K, V> e = table[index];
        while (e != null) {

            // 比拟 hash 值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {return e.value;}
            
            // 如果不相等,持续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数 key,value 很容易了解
     * 2 返回 V,咱们晓得,HashMap 有一个特点,* 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");
     * 前面的值会把后面的笼罩,如果呈现这种状况,返回旧值,在这里返回 "tom"
     */
    public V put(K key, V value) {
        //1 为了简略,key 不反对 null
        if (key == null) {throw new RuntimeException("key is null");
        }

        // 不间接用 key.hashCode(),咱们对 key.hashCode()再作一次运算作为 hash 值
        // 这个 hash()的办法我是间接从 HashMap 源码拷贝过去的。能够不必关怀 hash()算法自身
        // 只须要晓得 hash()输出一个数,返回一个数就行了。int hash = hash(key.hashCode());

        // 用 key 的 hash 值和数组的大小,作一次映射,失去应该寄存的地位
        int index = indexFor(hash, table.length);

        // 看看数组中,有没有已存在的元素的 key 和参数中的 key 是相等的
        // 相等则把老的值替换成新的,而后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            // 先比拟 hash 是否相等,再比拟对象是否相等,或者比拟 equals 办法
            // 如果相等了,阐明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        // 如果数组中没有元素的 key 与传的 key 相等的话
        // 把以后地位的元素保留下来
        QEntry<K, V> next = table[index];

        //next 有可能为 null,也有可能不为 null,不论是否为 null
        //next 都要作为新元素的下一个节点(next 传给了 QEntry 的构造函数)
        // 而后新的元素保留在了 index 这个地位
        table[index] = new QEntry<>(key, value, hash, next);

        // 如果须要扩容,元素的个数大于 table.length * 0.75 (别问为什么是 0.75,教训)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {resize();
        }

        return null;
    }

    // 扩容,元素的个数大于 table.length * 0.75
    // 数组扩容到原来大小的 2 倍
    private void resize() {
        // 新建一个数组,大小为原来数组大小的 2 倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        // 遍历旧数组,从新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            // 获取旧数组元素
            QEntry<K, V> e = src[j];

            // 开释旧数组
            src[j] = null;

            // 因为 e 是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                // 把 e 的下一个节点保留下来
                QEntry<K, V> next = e.next;

                // e 这个以后节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 地位上有可能是 null,也有可能不为 null
                // 不论是否为 null,都作为 e 这个节点的下一个节点
                e.next = newTable[i];

                // 把 e 保留在新数组的 i 的地位
                newTable[i] = e;

                // 持续 e 的下一个节点的同样的解决
                e = next;
            }
        }

        // 所有的节点都映射到了新数组上,别忘了把新数组的赋值给 table
        table = newTable;
    }

    // 对 hashCode 进行运算,JDK 中 HashMap 的实现,间接拷贝过去了
    static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 依据 h 求 key 落在数组的哪个地位
    static int indexFor(int h, int length) {// 或者  return h & (length-1) 性能更好
        // 这里咱们用最容易了解的形式,对 length 取余数,范畴就是[0,length - 1]
        // 正好是 table 数组的所有的索引的范畴

        h = h > 0 ? h : -h; // 避免正数

        return h % length;
    }

}

下面就是 QHashMap 的原理。上面咱们写一段测试代码来看下咱们的 QHashMap 能不能失常运行。测试代码如下:

 public static void main(String[] args) {QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key 一样,返回旧值,保留新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值 =" + oldValue);
        System.out.println("新值 =" + map.get("address"));
    }

输入如下:

tom
23
旧值 =beijing
新值 =shanghai

通过下面的简略的实现了 QHashMap, 还有好多功能没有实现,比拟 remove,clear,containsKey()等,还有遍历相干,有趣味的读者能够本人实现

正文完
 0