1.哈希表介绍

　　前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时，有序向量使得我们能使用二分查找法进行精确的查询((O(logN)对数复杂度，很高效)。
　　可人类总是不知满足，依然在寻求一种更高效的特定元素查询的数据结构，哈希表/散列表(hash table)就应运而生啦。哈希表在特定元素的插入，删除和查询时都能够达到O(1)常数的时间复杂度,十分高效。

1.1 哈希算法

　　哈希算法的定义：把任意长度的输入通过哈希算法转换映射为固定长度的输出，所得到的输出被称为哈希值(hashCode =?hash(input))。哈希映射是一种多对一的关系，即多个不同的输入有可能对应着一个相同的哈希值输出；也意味着，哈希映射是不可逆，无法还原的。

　　举个例子：我们有一个好朋友叫熊大,大家都叫他老熊。可以理解为是一个hash算法：对于一个人名，我们一般称呼为"老" + 姓氏(单姓) (hash(熊大) = 老熊)。同时，我们还有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚会时，都称呼他们为老熊就不太合适啦，因为这时出现了hash冲突。老熊这个称呼同时对应了多个人，多个不同的输入对应了相同的哈希值输出。

　　java在Object这一最高层对象中实现了hashCode方法，并允许子类重写更适应自身，冲突概率更低的hashCode方法。

1.2 哈希表实现的基本思路

　　哈希表存储的是key-value键值对结构的数据，其基础是一个数组。

　　由于采用hash算法会出现hash冲突，一个数组下标对应了多个元素。常见的解决hash冲突的方法有：开放地址法、重新哈希法、拉链法等等，我们的哈希表实现采用的是拉链法解决hash冲突。

　　采用拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或者桶(bucket)，并将数据存放在键值对节点(EntryNode)中。EntryNode除了存放key和value，还维护着一个next节点的引用。为了解决hash冲突，单个插槽内的多个EntryNode构成一个简单的单向链表，插槽指向链表的头部节点，新的数据将会插入当前链表的尾部。

　　key值不同但映射的hash值相同的元素在哈希表的同一个插槽中以链表的形式共存。

1.3 哈希表的负载因子(loadFactor)：

　　哈希表在查询数据时通过直接计算数据hash值对应的插槽，迅速获取到key值对应的数据，进行非常高效的数据查询。

　　但依然存在一个问题：虽然设计良好的hash函数可以尽可能的降低hash冲突的概率，但hash冲突还是不可避免的。当发生频繁的哈希冲突时，对应的插槽内可能会存放较多的元素，导致插槽内的链表数据过多。而链表的查询效率是非常低的，在极端情况下，甚至会出现所有元素都映射存放在同一个插槽内，此时的哈希表退化成了一个链表，查询效率急剧降低。

　　一般的，哈希表存储的数据量一定时，内部数组的大小和数组插槽指向的链表长度成反比。换句话说，总数据量一定，内部数组的容量越大(插槽越多)，平均下来桶链表的长度也就越小，查询效率越高。

　　同等数据量下，哈希表内部数组容量越大，查询效率越高，但同时空间占用也越高，这本质上是一个空间换时间的取舍。

　　哈希表允许用户在初始化时指定负载因子(loadFactor)：负载因子代表着存储的总数据量和内部数组大小的比值。插入新数据时，判断哈希表当前的存储量和内部数组的比值是否超过了负载因子。当比值超过了负载因子时，哈希表认为内部过于拥挤，查询效率太低，会触发一次扩容的rehash操作。rehash会对内部数组扩容，将存储的元素重新进行hash映射，使得哈希表始终保持一个合适的查询效率。

　　通过指定自定义的负载因子，用户可以控制哈希表在空间和时间上取舍的程度，使哈希表能更有效地适应用户的使用场景。

　　指定的负载因子越大，哈希表越拥挤(负载高，紧凑)，查询效率越低，空间效率越高。

　　指定的负载因子越小，哈希表越稀疏(负载小，松散)，查询效率越高，空间效率越低。

2.哈希表ADT接口

　　和之前介绍的链表不同，我们在哈希表的ADT接口中暴露出了哈希表内部实现的EntryNode键值对节点。通过暴露出去的public方法，用户在使用哈希表时，可以获得内部的键值对节点，灵活的访问其中的key、value数据(但没有暴露setKey方法，不允许用户自己设置key值)。

public interface Map <K,V>{
    /**
     * 存入键值对
     * @param key   key值
     *  value value
     * @return 被覆盖的的value值
     */
    V put(K key,V value);

    
     * 移除键值对
     *  被删除的value的值
     
    V remove(K key);

    
     * 获取key对应的value值
     *       对应的value值
     
    V get(K key);

    
     * 是否包含当前key值
     *       true：包含 false：不包含
     */
    boolean containsKey(K key);

    
     * 是否包含当前value值
     *  value   value值
     *         true：包含 false：不包含
      containsValue(V value);

    
     * 获得当前map存储的键值对数量
     *  键值对数量
     * int size();

    
     * 当前map是否为空
     *   true：为空 false：不为空
      isEmpty();

    
     * 清空当前map
     void clear();

    
     * 获得迭代器
     *  迭代器对象
     
    Iterator<EntryNode<K,V>> iterator();

    
     * 键值对节点 内部类
     * class EntryNode<K,1)">{
        final K key;
        V value;
        EntryNode<K,1)"> next;

        EntryNode(K key,V value) {
            this.key = key;
            this.value = value;
        }

         keyIsEquals(K key){
            if(this.key == key){
                return true;
            }

            if(key == null){
                //:::如果走到这步，this.key不等于null，不匹配
                false;
            }else{
                return key.equals(this.key);
            }
        }

        EntryNode<K,1)"> getNext() {
            return next;
        }

        void setNext(EntryNode<K,1)"> next) {
            this.next =public K getKey() {
             key;
        }

         V getValue() {
             setValue(V value) {
             value;
        }

        @Override
         String toString() {
            return key + "=" + value;
        }
    }
}

3.哈希表实现细节

3.1 哈希表基本属性：　　　　　　

class HashMap<K,V> implements Map<K,1)">{

    
     * 内部数组
     * private EntryNode<K,1)">[] elements;

    
     * 当前哈希表的大小
     * private  size;

    
     * 负载因子
     * float loadFactor;

    
     * 默认的哈希表容量
     * final static int DEFAULT_CAPACITY = 16;

    
     * 扩容翻倍的基数
     * int REHASH_BASE = 2
     * 默认的负载因子
     * float DEFAULT_LOAD_FACTOR = 0.75f========================================构造方法===================================================
    
     * 默认构造方法
     * 
    @SuppressWarnings("unchecked")
     HashMap() {
        this.size = 0;
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        elements = new EntryNode[DEFAULT_CAPACITY];
    }

    
     * 指定初始容量的构造方法
     *  capacity 指定的初始容量
     * public HashMap( capacity) {
         EntryNode[capacity];
    }

    
     * 指定初始容量和负载因子的构造方法
     *  capacity 指定的初始容量
     *  loadFactor 指定的负载因子
     * int capacity, loadFactor) {
         loadFactor;
        elements =  EntryNode[capacity];
    }
}