集合框架----源码解读HashMap篇（一）

1.HashMap官方介绍

基于哈希表的Map接口实现。该实现提供了所有可选的映射操作，并允许空值和空键。(HashMap类大致相当于Hashtable，除了它是非同步的，并且允许为空值。)这个类不保证映射的顺序;特别是，它不能保证顺序随时间的推移保持不变。
这个实现为基本操作(get和put)提供了恒定时间的性能，假设哈希函数将元素适当地分散到桶中。在集合视图上迭代所需的时间与HashMap实例的“容量”(桶的数量)加上它的大小(键-值映射的数量)成正比。因此，如果迭代性能很重要，就不要将初始容量设置得太高(或负载因子设置得太低)。
HashMap实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中桶的数量，初始容量是创建哈希表时的容量。负载系数衡量的是在哈希表的容量自动增加之前允许达到的满度。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新哈希(即重新构建内部数据结构)，以便哈希表的桶数约为原来的两倍。
作为一般规则，默认负载系数(.75)在时间和空间成本之间提供了很好的权衡。较高的值会减少空间开销，但会增加查找成本(反映在HashMap类的大多数操作中，包括get和put)。在设置映射的初始容量时，应考虑映射中期望的条目数及其负载因子，以减少重哈希操作的次数。如果初始容量大于最大条目数除以负载因数，则不会发生重哈希操作。
如果要将许多映射存储在一个HashMap实例中，那么用足够大的容量创建它将允许更有效地存储映射，而不是让它根据需要执行自动重哈希以增长表。注意，在同一个hashCode()中使用多个键肯定会降低任何哈希表的性能。为了改善影响，当键具有可比性时，该类可以使用键之间的比较顺序来帮助打破束缚。
注意，这个实现不是同步的。如果多个线程并发访问一个哈希映射，并且至少有一个线程在结构上修改了映射，那么它必须从外部同步。(结构修改是添加或删除一个或多个映射的任何操作;仅仅改变与实例中已经包含的键相关联的值并不是结构修改。)这通常是通过在自然封装映射的某些对象上同步来实现的。如果不存在这样的对象，则应该使用集合“包装”映射。synchronizedMap方法。这最好在创建时完成，以防止意外的不同步访问映射:
映射m =集合。synchronizedMap(新HashMap(…));
这个类的所有“集合视图方法”返回的迭代器都是快速失败的:如果映射在迭代器创建后的任何时间被结构修改，除了通过迭代器自己的remove方法以外，迭代器将抛出ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在未来不确定的时间发生任意的、不确定的行为。
注意，迭代器的快速失败行为不能得到保证，因为一般来说，在存在不同步的并发修改时，不可能做出任何硬保证。快速失败迭代器尽可能地抛出ConcurrentModificationException。因此，编写一个依赖于此异常的程序是错误的:迭代器的快速失败行为应该只用于检测错误。
这个类是Java集合框架的成员。

2.equals方法

 在学习hashMap之前我需要学一下equals的底层原理，创建一个对象，两个完全相等的对象比较结果输出的确是false？ 进入equals方法

 进入这个方法我们可以得知 equal方法默认是比较两个对象的内存地址是否相等

 当我们两个字符串相比较输出结果是true，这里之所以是true，是因为string方法重写了equal方法

我们在string方法也发现了equal方法

 这个方法表达的意思很简单，先判断两个对象的内存地址是否一样，再判断两个字符串的长度，最后判断两个字符串的值是否相等，看到这里 你应该猜到 字符串的底层就是一个字节数组

 3.HashCode方法

HashCode方法就是把堆内存地址转换成整数类型，在重写equal方法的同时也要重写hashCode方法

1.如果equal方法比较两个对象相等，则HashCode值也相等

2.如果两个对象的HashCode值相等，但是equal值不一定相等（hash冲突）

 a底层就是97，但是我们人知道97和a是两个东西，但是机器不知道，字符一共有65535个，a就放在97这个位置。机器会任务这个两个就是同一个东西，这就是常说的哈希冲突

 4.HashMap底层原理

主要讲的1.7的HashMap，hashMap 底层就是靠Entry对象进行存储对象的，下图我们可以得知，这里用到了单向列表

 我们之前学过ArrayList，假如我们把Entry放进ArrayList集合厉害呢，来实现HashMap

package com.example.list.list;
 
 
import java.util.ArrayList;
 
public class AHashMap {
    /**
     * 基于ArrayList的HashMap 的查询效率极低
     * 可以保证存放键值对是有序的，不是散列的
     */
    //创建一个容器存放
    private ArrayList> arrayListEntry = new ArrayList>();
 
    /**
     * Entry存放键值对
     */
    class Entry {
        K k;
        V v;
 
        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
 
    public void put(K k, V v) {
        arrayListEntry.add(new Entry<>(k, v));
 
    }
 
    public V get(K k) {
        for (Entry entry : arrayListEntry) {
            if(entry.k.equals(k)){
                return entry.v;
            }
            
        }
        return null;
    }
 
 
}

 为了解决查询效率低的问题，这里就不得不说一下Key的Hash算法 我用java1.7实现hashmap数组+链表的结构，讲解一下Key的Hash算法 

1.根据key的hashCode取entrys.length 余数就是该key的存放位置
int index = k.hashCode() % entrys.length;
这一行就是key的hash ，Map之所以高效就是利用直观哈希值取余的算法实现高效的查询，用了哈希算法会出现一个致命的问题就是哈希冲突，我们下面的HashMap只是基于数组实现的，发生哈希冲突会把会把之前的一样的key的值覆盖。我学些过Map知道K是唯一的，HashMap又是这么解决的呢？

package com.example.list.list;
 
 
public class HHashMap {
 
    private Entry[] entrys = new Entry[10000]; //这里我写死，不进行扩容
 
 
    /**
     * Entry存放键值对
     */
    class Entry {
        K k;
        V v;
 
        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
 
    /**
     * 1.7 数组+链表实现HashMap
     * 1.8 数组+链表+红黑树来实现HashMap
     *
     * @param k
     * @param v
     */
 
    public void put(K k, V v) {
        //1.根据key的hashCode取entrys.length 余数就是该key的存放位置
        int index = k.hashCode() % entrys.length;
        entrys[index] = new Entry<>(k, v);
    }
 
    public V get(K k) {
        int index = k.hashCode() % entrys.length;
        return (V)entrys[index].v;
 
 
    }
 
 
}

在1.7为了解决哈希冲突问题，引入了链表，假设第一次存入的a ，a的HashCode值是97，我们现在把他放在97这个位置。第二次我们存入数字的97,，在1.7版本中第一步拿着这97对应的 HashCode值去找，发现上面有一个a，他就放在a,的下方（不是在98），形成链表。 假如没有发生哈希冲突，HashMap还是数组，有了冲突就会变成 数组+链表（冲突的放在链表）的组合。

 

如果debug运行现在存放的put的哈希冲突问题已经解决了，下面我需要对get方法进行升级，确保我们查的元素就是我们 要的值

package com.example.list.list;
 
 
 
public class HHashMap {
 
    private Entry[] entrys = new Entry[10000]; //这里我写死，不进行扩容
 
 
    /**
     * Entry存放键值对
     */
    class Entry {
        K k;
        V v;
        int hash; //hash值
        Entry next;  //下一个节点
 
        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
 
    /**
     * 1.7 数组+链表实现HashMap
     * 1.8 数组+链表+红黑树来实现HashMap
     *
     * @param k
     * @param v
     */
 
    public void put(K k, V v) {
        /**
         * 1.根据key的hashCode取entrys.length 余数就是该key的存放位置
         * 2.先判断该index对应的index位置
         * 3.如果能够取出Entry对象,则发生哈希冲突，存放在他的下方
         */
 
        int index = k.hashCode() % entrys.length;
        Entry oldEntry = entrys[index];
        if (oldEntry == null) {
            entrys[index] = new Entry<>(k, v);
 
        } else {
            oldEntry.next = new Entry<>(k, v);
        }
    }
 
    public V get(K k) {
        int index = k.hashCode() % entrys.length;
        return (V) entrys[index].v;
 
 
    }
 
    public static void main(String[] args) {
        HHashMap map = new HHashMap();
        map.put("a", "a");
        map.put(97, 97);
        System.out.println(map.get(97));
        
 
    }
 
 
}

我第一步去算去对应的hash值，第二步再去遍历这个链表，把值和哈希值相等的数就是我们要查找的数

package com.example.list.list;
 
 
public class HHashMap {
 
    private Entry[] entrys = new Entry[10000]; //这里我写死，不进行扩容
 
 
    /**
     * Entry存放键值对
     */
    class Entry {
        K k;
        V v;
        int hash; //hash值
        Entry next;  //下一个节点
 
        public Entry(K k, V v, int hash) {
            this.k = k;
            this.v = v;
            this.hash = hash;
        }
    }
 
    /**
     * 1.7 数组+链表实现HashMap
     * 1.8 数组+链表+红黑树来实现HashMap
     *
     * @param k
     * @param v
     */
 
    public void put(K k, V v) {
        /**
         * 1.根据key的hashCode取entrys.length 余数就是该key的存放位置
         * 2.先判断该index对应的index位置
         * 3.如果能够取出Entry对象,则发生哈希冲突，存放在他的下方
         */
        int hash=k.hashCode();
        int index = hash % entrys.length;
        Entry oldEntry = entrys[index];
        if (oldEntry == null) {
            entrys[index] = new Entry<>(k, v,hash);
 
        } else {
            oldEntry.next = new Entry<>(k, v,hash);
        }
    }
 
    public V get(K k) {
 
        int hash=k.hashCode();
        int index = hash % entrys.length;
        //遍历链表,把hash值和值相等的
        for (Entry entry = entrys[index]; entry != null; entry = entry.next) {
        if(entry.hash==hash&&entry.k.equals(k)){
            return entry.v;
        }
        }
        return null;
 
 
    }
 
    public static void main(String[] args) {
        HHashMap map = new HHashMap();
        map.put("a", "a");
        map.put(97, 97);
        System.out.println(map.get(97));
 
 
    }
 
 
}

 其实这里还存在一个潜在问题，假如冲突的元素非常多呢，会导致链表特别长，如果有学习过链表我们就会会知道，这样我们的查询效率就会很慢，为了解决这个问题就引入红黑树。红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。

5.HashMap 散列表为什么是无序的

回到这个问题，其实根本原因就是hash冲突造成的，数组index我们将当做根，当HashMap进行遍历会把在index等于0的下面的链表也遍历出来，后面的也一样我们存放链表的数据可能比index等于2后，但是依然会先遍历出来