顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( $\log_{2}N$ )，搜索的效率取决于搜索过程中元素的比较次数
哈希表作为一个非比较的方法去查找和删除元素，这是和利用比较的方法最不同的地方，它的好处也正是在于不用比较，大大的降低了时间复杂（O(1)）

一，哈希表概念

1.概念

不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函
数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

2.初次简单模拟

模拟分析向该状态下的表格里插入和查找元素

0	1	2	3	4	5	6	7	8	9
	1				5	6		8	9

假设待插入的元素为红色单元格的数字，表格是要插入的地方（一个数组array）

一一映射关系（HashFunc）：index = value % array.length

插入元素：

计算带插入元素的在表格中的位置index
将元素插入到表格中index的位置

查找元素：

查找这个元素在这个表格中可能存在的位置（有可能不存在）
到相应位置去获取元素

3.模拟总结

可以发现在实际运用中，对于数组来说，插入和查找的时间复杂度就是O(1)

在上面的简单模拟中：

存储元素的表格（或者说是数组）就是哈希表，也称散列表
index所表示的就是这个元素的哈希地址
映射关系（HashFunc）：index = value % array.length 这是哈希函数或者称为散列函数

二，哈希冲突（哈希碰撞）

1.概念

在上面的模拟过程中，哈希展现了其精妙之处，但是也存在问题，借用上面的模拟，如果现在有一个数字是99，它的哈希地址和9的哈希地址是一模一样的，那么现在强行插入元素，之前的元素就会被替换掉，所以，就不能直接插入，因此，把这种冲突叫做哈希冲突（哈希碰撞）
简而言之就是，不同的元素通过哈希函数计算出来了相同的哈希地址，这些元素称为同义词

2.分析

初步分析：

通过了解可以发现，哈希表的容量往往是小于元素个数的，因此，可以说哈希冲突是必然发生的，只能说，我们设计的哈希函数要尽可能的要做到避免冲突
我们可以把不发生哈希冲突理解为这个哈希函数的渐近线，而设计出来的哈希函数就是再精妙，它也是在无线逼近渐进线，而不是可以等于这个渐进线所在的值
避免发生哈希冲突，哈希函数的设计思想

避免冲突时的哈希函数设计：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见的哈希函数：

1. 直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

2. 除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数
通常应用于关键字长度不等时采用此法

6. 数学分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址
数学分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

3.解决

1.闭散列

闭散列：当发生哈希冲突时，从发生哈希冲突的位置开始寻找下一个空位置
寻找空位置也有两种方法：

线性探测

当发生哈希冲突时，从发生冲突的位置开始依次往后寻找，如果找到了哈希表的末尾，在接着从头开始继续寻找
此时就需要添加两个标记，来对每个位置里是否有元素进行标记，有就是Exist，没有就是Empty，进行查找，当添加完成后，需要将这个位置的标记进行更改
查找元素时，需要添加一个Delete的标记，因为存在一种情况（假设现在在上面这个数组当中查找9，我们需要计算相应的哈希地址去寻找，所以，去9号位置找，找到了并删除，第二次要找99，当来到9号位置时，却发现是空的，系统会自动判定，我们的数组当中没有99这个元素，但实际上有，只是因为发生了哈希冲突，我们将99这个元素放到了下一个空位置而已）因此，我们添加一个delete的删除标记，是为了告诉计算机，我们还有发生了哈希冲突的元素，需要对别的位置进行查找
那万一存满了呢？实际上是不会放满的，那么放的少了------>空间利用率低，放得多了------>哈希冲突概率高了
哈希的负载因子（载荷因子）：哈希表中存放的有效元素个数 / 哈希表的容量；负载因子越小，发生哈希冲突的概率越小（在Java中大约是0.75左右）
优点：处理冲突的方式简单；缺点：容易产生数据的堆积

缺点示例：

哈希函数：index = value % array.length

红色数字表示：发生了哈希冲突时，放置的元素

11 21 22 33 44 55

0 1 2 3 4 5 6 7 8 9
11 21 22 33 44 55

可以很直观地观察到，一冲突，后面元素若是此种顺序，堆积的更加严重！！！

二次探测：

H(i) = H(0) + i ^ 2 H(0)表示第一此计算出来的哈希地址，i 表示从1 到 9 的数
优点：解决了线性探测的堆积问题；缺点：当表格中的元素不断增多时，需要查找的次数也变得多了
当表的长度为质数且表负载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容
闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

2.开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
简单点说就是数组 + 链表的方式存储

待插入的元素：

哈希函数：HashFunc(key) = key % capacity capacity为哈希表的容量

三，模拟实现哈希桶（开散列）

方法	解释
V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

以上就是我们要实现的方法

模拟实现的准备工作

1.定义哈希表中的结点

2.构造方法

3.哈希地址的计算方法


public class TestHashMap {
    public static class ListNode{
        int key;
        Integer value;
        ListNode next;
 
        public ListNode(int key,Integer value){
            this.key = key;
            this.value = value;
        }
    }
 
    ListNode[] table;
    int size;
 
    public TestHashMap(int initCapacity){
        initCapacity = initCapacity <= 0 ? 16 : initCapacity;
        table = new ListNode[initCapacity];
    }
 
    private int hashFunc(int key){
        return key % table.length;
    }

1.操作之添加 / 插入


    //操作------>插入/添加
    public Integer put(int key,Integer value){
        //计算key的哈希地址
        int index = hashFunc(key);
        //查找元素是否存在
        ListNode cur = table[index];
        while(cur != null){
            if(cur.key == key){
                Integer oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
            cur = cur.next;
        }
 
        //没有元素重复
        ListNode newNode = new ListNode(key,value);
        newNode.next = table[index];
        table[index] = newNode;
 
        size++;
        return value;
    }

2.操作之获取key的value


    //操作------> 获取key的value
    public Integer get(int key){
        //计算key的哈希地址
        int index = hashFunc(key);
 
        //查找key
        ListNode cur = table[index];
        while(cur != null){
            if (cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
 
        return null;
    }

3.操作之 key存在返回key对应的value，key不存在返回默认值


    //操作 ------> key存在返回key对应的value，key不存在返回默认值
    public Integer getOrDefault(int key,int value){
        if(get(key) != null){
            return get(key);
        }else{
            return value;
        }
    }

4.操作之删除key


    //操作 ------>删除key
    public void remove(int key){
        if (get(key) != null){
            //计算哈希地址
            int index = hashFunc(key);
            ListNode cur = table[index];
            ListNode prev = null;
 
            while(cur != null){
                if(cur.key == key){
                    if(cur == table[index]){
                        table[index] = cur.next;
                        size--;
                        return;
                    }else{
                        prev.next = cur.next;
                        size--;
                        return;
                    }
                }else{
                    prev = cur;
                    cur = cur.next;
                }
            }
        }
    }

5.操作之是否包含key


    //操作 -----> 是否包含key
    public boolean containsKey(int key){
        if(get(key) != null){
            return true;
        }
        return false;
    }

6.操作之是否包含value


    //操作 ------> 是否包含value
    public boolean containsValue(int value){
        for(int index = 0;index < table.length;index++){
            ListNode cur = table[index];
 
            while(cur != null){
                if(cur.value == value){
                    return true;
                }
                cur = cur.next;
            }
        }
        return false;
    }

7.测试代码（模拟实现的全部代码）


public class TestHashMap {
    public static class ListNode{
        int key;
        Integer value;
        ListNode next;
 
        public ListNode(int key,Integer value){
            this.key = key;
            this.value = value;
        }
    }
 
    ListNode[] table;
    int size;
 
    public TestHashMap(int initCapacity){
        initCapacity = initCapacity <= 0 ? 16 : initCapacity;
        table = new ListNode[initCapacity];
    }
 
    private int hashFunc(int key){
        return key % table.length;
    }
    //操作------>插入/添加
    public Integer put(int key,Integer value){
        //计算key的哈希地址
        int index = hashFunc(key);
        //查找元素是否存在
        ListNode cur = table[index];
        while(cur != null){
            if(cur.key == key){
                Integer oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
            cur = cur.next;
        }
 
        //没有元素重复
        ListNode newNode = new ListNode(key,value);
        newNode.next = table[index];
        table[index] = newNode;
 
        size++;
        return value;
    }
 
    //操作------> 获取key的value
    public Integer get(int key){
        //计算key的哈希地址
        int index = hashFunc(key);
 
        //查找key
        ListNode cur = table[index];
        while(cur != null){
            if (cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
 
        return null;
    }
 
    //操作 ------> key存在返回key对应的value，key不存在返回默认值
    public Integer getOrDefault(int key,int value){
        if(get(key) != null){
            return get(key);
        }else{
            return value;
        }
    }
 
    //操作 ------>删除key
    public void remove(int key){
        if (get(key) != null){
            //计算哈希地址
            int index = hashFunc(key);
            ListNode cur = table[index];
            ListNode prev = null;
 
            while(cur != null){
                if(cur.key == key){
                    if(cur == table[index]){
                        table[index] = cur.next;
                        size--;
                        return;
                    }else{
                        prev.next = cur.next;
                        size--;
                        return;
                    }
                }else{
                    prev = cur;
                    cur = cur.next;
                }
            }
        }
    }
 
    //操作 -----> 是否包含key
    public boolean containsKey(int key){
        if(get(key) != null){
            return true;
        }
        return false;
    }
    //操作 ------> 是否包含value
    public boolean containsValue(int value){
        for(int index = 0;index < table.length;index++){
            ListNode cur = table[index];
 
            while(cur != null){
                if(cur.value == value){
                    return true;
                }
                cur = cur.next;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        TestHashMap hb = new TestHashMap(10);
        hb.put(1,1);
        hb.put(2,2);
        hb.put(3,3);
        hb.put(6,6);
        hb.put(5,5);
        hb.put(4,4);
        hb.put(10,null);
 
        System.out.println(hb.size);
        System.out.println(hb.get(1));
 
        System.out.println(hb.get(10));
        hb.put(10,10);
        System.out.println(hb.get(10));
        hb.put(10,20);
        System.out.println(hb.get(10));
 
        System.out.println(hb.getOrDefault(20,-1));
        
        hb.remove(6);
        System.out.println(hb.size);
        
        if(hb.containsKey(10)){
            System.out.println("10 在哈希表中");
        }else{
            System.out.println("10 不在哈希表中");
        }
 
        if(hb.containsValue(100)){
            System.out.println("100 在哈希表中");
        }else{
            System.out.println("100 不在哈希表中");
        }
    }
}

四，总结

常见问题：

1.链表中结点不适宜过多？

答案是肯定的，肯定不能过多，不然会失去哈希桶本身的优势和存在的意义

2.大部分元素集合到一个链表当中怎么办？（以上面实现开散列为例子，假设key为 10 20 30 40 50 60 70 80 90）

进行扩容，并对哈希表重新进行开散列，就有可能将元素重新分布

标准库中的扩容

1.默认初始容量为16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2.最大容量为2 ^ 30


/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

3.HashMap的默认负载因子是0.75


/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

4.链表和红黑树相互转化

当链表中节点个数超过8时，会将链表转化为红黑树
若红黑树中节点小于6时，红黑树退还为链表
如果哈希桶中某条链表的个数超过8，并且桶的个数超过64时才会将链表转换为红黑树，否则直接扩容


/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
// 若链表中节点个数超过8时，会将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
// 若红黑树中节点小于6时，红黑树退还为链表
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
// 如果哈希桶中某条链表的个数超过8，并且桶的个数超过64时才会将链表转换为红黑树，否则直接扩容
static final int MIN_TREEIFY_CAPACITY = 64;

5.哈希函数


/*
1. key如果为空，返回的是0号桶
2. key如果不为空，返回该key所对应的哈希码，从该位置可以看出，如果key是自定义类型，必须要重写 
   Object类的hashCode方法
3. 高16bit不变，低16bit和高16bit做了一个异或，主要用于当hashmap 数组比较小的时候所有bit都参与运 
   算了目的是减少碰撞
4. 获取到哈希地址后，计算桶号的方式为：index = (table.length - 1) & hash
5. 通过除留余数法方式获取桶号，因为Hash表的大小始终为2的n次幂，因此可以将取模转为位运算操作，提 
   高效率，这也就是为什么要按照2倍方式扩容的一个原因
hash&(table.length-1)     二进制      index        key%(table.length)     index
     4  & 15             100&1111     100             4  % 16              4
     13 & 15             1101&1111    1101            13 % 16             13
     19 & 15             10011&1111   11              19 % 16              3
通过上述方式可知，实际上hashcode的很多位是用不上的，因此在HashMap的hash函数中，才使用了移位运算，只取了hashcode的前16位来做映射。2^15=65536 已经是很大的数字了，另一方面&操作比取模效率更高
*/
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

6.下一次扩容大小计算


// 每次都是将cap扩展到大于cap最近的2的n次幂
static final int tableSizeFor(int cap) {
       int n = cap - 1;
       n |= n >>> 1;
       n |= n >>> 2;
       n |= n >>> 4;
       n |= n >>> 8;
       n |= n >>> 16;
       return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍

7.构造方法


// 构造方法一：带有初始容量的构造，负载因子使用默认值0.75
public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 构造方法二：
public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 构造方法一：带有初始容量和初始负载因子的构造
public HashMap(int initialCapacity, float loadFactor) {
       // 如果容量小于0，抛出非法参数异常
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
       // 如果初始容量大于最大值，用2^30代替
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       // 检测负载因子是否非法，如果负载因子小于0，或者负载因子不是浮点数，抛出非法参数异常
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
       // 给负载因子和容量赋值，并将容量提升到2的整数次幂
       // 注意：构造函数中并没有给
       this.loadFactor = loadFactor;
       this.threshold = tableSizeFor(initialCapacity);
}
/*
不同于Java7中的构造方法，Java8对于数组table的初始化，并没有直接放在构造器中完成，而是将table数组的构造延迟到了resize中完成
*/

8.LinkedHashMap

LinkedHashMap继承自HashMap，并实现了Map接口
LinkedHashMap底层使用了哈希桶和双向链表两种结构
LinkedHashMap需要重写HashMap中的：afterNodeInsertion/afterNodeAcess/afterNodeRemove等方法
LinkedHashMap使用迭代器访问时，可以保证一个有序的结果，注意此处的有序不是自然有序，而是元素的插入次序。另外，当向哈希表中重复插入某个键的时候，不会影响到原来的有序性。也就是说，假设你插入的键的顺序为1、2、3、4，后来再次插入2，迭代时的顺序还是1、2、3、4，而不会因为后来插入的2变成1、3、4、2
LinkedHashMap可以作为LRU来使用,但是要重写removeEldestEntry方法

9.resize扩容
在Java8的扩容中，不是简单的将原数组中的每一个元素取出进行重新hash映射，而是做移位检测。所谓移位检测的含义具体是针对HashMap做映射时的&运算所提出的，通过上文对&运算的分析可知，映射的本质即看hash值的某一位是0还是1，当扩容以后，会相比于原数组多出一位做比较，由多出来的这一位是0还是1来决定是否进行移位，而具体的移位距离，也是可知的，及位原数组的大小，我们来看下表的分析，假定原表大小为16

HashCode(Java8中只使用高16
位）
size=16 size=32 移位
情况
0101 1010 0011 1101 0101101000111101&1111 0101101000111101&11111 向前
移动
16位
1011 0111 1000 0101 1011011110000101&1111 1011011110000101&11111 不移
动
1110 0100 0001 0001 1110010000010001&1111 1110010000010001&1111 向前
移动
16

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/739925

哈希表总结

引言

一，哈希表概念

1.概念

2.初次简单模拟

3.模拟总结

二，哈希冲突（哈希碰撞）

1.概念

2.分析

初步分析：

避免冲突时的哈希函数设计：

常见的哈希函数：

3.解决

1.闭散列

2.开散列

三，模拟实现哈希桶（开散列）

模拟实现的准备工作

1.定义哈希表中的结点

2.构造方法

3.哈希地址的计算方法

1.操作之添加 / 插入

2.操作之获取key的value

3.操作 之 key存在返回key对应的value，key不存在返回默认值

4.操作之删除key

5.操作之是否包含key

6.操作之是否包含value

7.测试代码（模拟实现的全部代码）

四，总结

常见问题：

标准库中的扩容

3.操作之 key存在返回key对应的value，key不存在返回默认值