数据结构之散列表

这是我参与更文挑战的第21天，活动详情查看：更文挑战

什么是散列表

HashTable类也叫HashMap类，是Dictionary类的一种散列表实现方式。

散列表：顾名思义也就是离散的或者零散，即不连贯的列表，也可以类比于离散数组。

散列算法的作用是尽可能的在数据结构中找到一个值。如果使用散列函数就知道值的具体位置，因此能快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。

创建一个散列表

我们使用数组来表示该数据结构。并添加其基础的方法：

• put(key, value): 向散列表增加一个新的项（也能更新散列表）。
• remove(key): 根据键值从散列表中移除值。
• get(key): 返回根据键值检索到的特定的值。

function HashTable () {
    let table = []
    // 先实现散列函数，其是HashTable类中的一个私有方法
    let loseloseHashCode = function (key) {
        let hash = 0
        // 使用组成key的每个字符的ASCII码值
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        return hash % 37
    }
    // 根据给定的key通过散列函数计算出它在表中的位置，并将value参数添加到计算出来的位置上。
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        // 类似于数组的下标
        table[position] = value
    }
    
    this.get = function (key) {
        return table[loseloseHashCode(key)]
    }
    // 找到元素所在的位置将其置为undefined即可，
    this.remove = function (key) {
        table[loseloseHashCode(key)] = undefined
    }
}
复制代码

上述代码中，对于散列表来说，不需要像数组一样在移除元素的时候将其位置也移除。由于元素分布在整个数组范围内，一些位置会没有任何元素占据，并默认为undefined值。我们也不能将位置本身从数组中移除（这会改变其他元素的位置），否则当下次需要获得或移除一个元素的时候，这个元素会不在我们用散列函数求出的位置上。

散列表和散列集合

• 散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是散列函数。
• 散列集合不再添加键值对，而是只插入值而没有键。
• 散列集合只存储唯一的不重复的值。