1 散列

散列表（HashTable），我们平时也会称它为“哈希表”，是一种经常使用的数据结构，也是典型的空间换时间的思路的体现。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

假如我们有 19 名选手参加学校运动会。为了方便记录成绩，每个选手胸前都会贴上自己的参赛号码，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位是依次递增的编号 1 到 19。

尽管不能直接把编号作为数组下标，但我们可以截取参赛编号的后两位作为数组下标来存取选手信息。这就是典型的散列思想。其中，参赛选手的编号叫做key，参赛编号转化为数组下标的映射方法就叫作散列函数，而散列函数计算得到的值就是散列值，时间复杂度是 O(1)。

)

2 散列函数

散列函数在散列表中起着非常关键的作用，顾名思义就是一个函数，可以将其定义为 hash(key)，key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

上述例子中，编号的后两位就是数组下标，所以 hash(key) 就等于 key，如下：

typescript复制代码int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = Integer.parseInt(lastTwoChars);
  return hashValue;
}

如果参赛选手的编号是随机生成的 6 位数字，又或者用的是 a 到 z 之间的字符串，我们可以依据以下三点来设计散列函数：

散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第三点要求看起来合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。此外，因为数组的存储空间有限，也会加大散列冲突的概率。所以针对散列冲突问题，我们需要通过其他途径来解决。

3 散列冲突

3.1 开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。比较简单的探测方法是线性探测。

当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

)

在散列表中查找元素的过程类似插入过程。通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。相等则说明就是要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。

)

散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。对于使用线性探测法解决冲突的散列表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。

解决方案是将删除的元素，特殊标记一下。当线性探测查找的时候，遇到特殊标记的空间时，并不是停下来，而是继续往下探测。

)

线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。

为了尽可能保证散列表的操作效率，一般情况下，会保证散列表中有一定比例的空闲槽位，空位的多少则用负载因子（load factor）表示。

负载因子 = 填入表中的元素个数 / 散列表的长度

负载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

3.2 链表法

链表法是一种更加常用的散列冲突解决办法。在散列表中，每个“槽（slot）”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。

)

当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。

关于查找和删除操作的时间复杂度，和链表的长度k成正比，即O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

4 手写HashTable底层实现

哈希表存储的是键值对，所以需要两个泛型来分别表示key和value的数据类型，key的数据类型必须实现hashcode()方法，不过由于java中所有的类都继承了Object类，所以默认所有的类都实现了hashcode()方法。

关键在于hashcode()是不是我们想要的。

另外我们也可以考虑哈希表的动态空间处理，当每个位置的平均哈希冲突超过上界时则扩容，小于下界时则缩容。

上面介绍链表法时，整个槽slot可以看做是一个TreeMap数组，数组的每一个位置存储了一个链表或者红黑树，所以构造函数可以实现如下：

arduino复制代码public class HashTable<K, V> {

    /**
    *    容忍度上界
    */ 
    private static final int upperTol = 10;

    /**
    *    容忍度下界
    */ 
    private static final int lowerTol = 2;

    /**
    *    初始容量
    */
    private static final int initCapacity = 7;

    private TreeMap<K, V>[] hashtable;
    // 长度（素数）
    private int M;
    // 已经存储了多少元素
    private int size;

    public HashTable(int M){
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        // 对每一个TreeMap进行初始化
        for (int i = 0; i < M; i ++)
            hashtable[i] = new TreeMap<>();
    }

    public HashTable(){
        this(initCapacity);
    }

}

在实现哈希表的增删改查之前，我们需要定义辅助方法hash用于计算要存储的位置，由于数组的索引是从0开始的，所以我们要避免负数的出现：

arduino复制代码private int hash(K key){
    return key.hashCode() & 0x7fffffff % M; 
}

public int getSize(){ return size; }

向哈希表中添加键值对：

根据key计算要插入的位置（对应一个TreeMap）
如果TreeMap中已经存在这个key的话就进行value的更新
如果TreeMap中不存在这个key的话则进行数据添加
当元素过多时进行扩容操作

arduino复制代码 public void add(K key, V value){
        // 计算要插入的位置
        TreeMap<K, V> map = hashtable[hash(key)];
        // key已存在
        if (map.containsKey(key))
            map.put(key, value);
        else {
            // key不存在
            map.put(key, value);
            size ++;
        
            // 满足条件则扩容
            if (size >= upperTol * M)
                resize(2 * M);
        }
    }

删除操作：

根据key计算要删除key对应的位置（对应一个TreeMap）
判断是否包含这个key，存在的话则删除
当元素过少时进行扩容操作

ini复制代码public V remove(K key){
        // 计算要删除的位置
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        // 存在则删除
        if (map.containsKey(key)){
            ret = map.remove(key);
            size --;    
            
            // 一定情况下缩容
            if (size < lowerTol * M && M / 2 >= initCapacity)
                resize(M / 2);
        }
        return ret;
    }

修改操作：

根据key计算要进行修改的位置（对应一个TreeMap）
存在该元素时则修改

vbnet复制代码public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if (!map.containsKey(key))
            throw new IllegalArgumentException(key + " doesn't exist!");
        map.put(key, value);
    }

查询操作：

vbnet复制代码    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }

动态空间处理方法：

类似于动态数组，开辟一个新的TreeMap数组，将原始数据全都放入到新的TreeMap数组中即可，注意hash()函数计算时需要使用新的Map长度。

ini复制代码
    private void resize(int newM){
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i ++)
            newHashTable[i] = new TreeMap<>();

        int oldM = M;
        // hash()函数需要新的M值
        this.M = newM;  
        for (int i = 0; i < oldM; i ++){
            TreeMap<K, V> map = hashtable[i];
            for (K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }

        this.hashtable = newHashTable;
    }

}

测试：

读取一本英文著作《傲慢与偏见》，统计词频，查看性能。

arduino复制代码public static void main(String[] args) {
        System.out.println("Pride and Prejudice");
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)){         
            // HashTable
            startTime = System.nanoTime();
            HashTable<String, Integer> ht = new HashTable<>(131071);
            for (String word : words) {
                if (ht.contains(word))
                    ht.set(word, ht.get(word) + 1);
                else
                    ht.add(word, 1);
            }
            for (String word: words)
                ht.contains(word);
            endTime = System.nanoTime();
            time = (endTime - startTime)/1000000000.0;
            System.out.println("HashTable: " + time);
        }
    }

执行用时：

)

5 *应用

有了哈希表我们可以应用于数据可以无序存储但需要快速查询的场景。比如：Word 文档中单词拼写检查功能。

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。

6 阿里面试题

HashMap的初始容量是16，并且容量都维持在n次方原因：性能考虑。只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞（hash值 & length-1）

负载因子越小，内存占用越多，查询时间越快；内存吃紧的话可以调大负载因子，冲突概率会增加。

HashMap对key的要求：不可变的，比如String被final修饰的。

HashMap存在线程安全问题，1.8之前使用头插法会产生环。我们可以使用ConcurrentHashMap来避免线程安全问题。

1.7之前：采用了分段锁机制来储存数据。在集合对象中储存一个segment数组，把集合的元素分为16个分段，每个分段上储存一个HashEntry数组及对应的链表，每个HashEntry数组就相当于一个HashMap。

)

当触发锁时每一个segment中都会有一个独立的锁，而不会将整个对象锁住，所以多线程操作时每个segment中的数据不会相互影响，从而保证了效率，当然，这样储存的版本还有着不少的问题，如最多并发只有16个，结构过于臃肿等等，随着版本的迭代，在jdk1.8时更改了ConcurrentHashMap的结构，使之更加完善。

1.8之后：利用CAS原理（比较交换原理）解决并发问题，其中有三个数：所存的值V，预期的值A，要变换成为的新值B。当A和V相同时，V会修改成B，否则不进行操作。这样就能较好的解决线程安全的问题。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有