数据结构之散列表（二）-一一网

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

我们在上一篇散列表中简单的实现了散列函数和散列表。仔细想来，我们简单实现的散列函数会存在问题，就是可能会产生一些重复的hash值出来，也就会造成冲突。也就是散列表的冲突。

散列表的冲突

在某些情况下，一些键会有相同的散列值。

而不同的值在散列表中对应相同位置的时候，我们就称之为冲突。

let hash = new HashTable()
// 添加值并打印输出的话可能会得到相同的hash值
has.put('Tyrion', 'aaa@qq.com') // 16
has.put('Aaron', 'bbb@qq.com') // 16
复制代码

一旦发生冲突，那么后添加的值会把前一个添加的值覆盖掉。以致于会造成数据的丢失，而这显然不是我们想要的结果。

冲突的解决

1. 分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法。但是在HashTable实例之外还需要额外的存储空间。

也就是说对于普通的散列表，本身在某个位置存储的是一个值，而我们已经知道链表是有序的元素的集合，?由存储元素本身的值和指向下一个值的引用，那么我们将某个位置本来要存储的值换成链表的形式，这就意味着我们在这个位置可以存放多个值了，这就说我们所说的分离链接

为了实现一个使用了分离链接的HashTable实例，我们需要一个新的辅助类来表示将要加入LinkedList实例的元素。我们称之为ValuePair类（在HashTable内部定义）：

function HashTable () {
    let table = []
    
    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存储在一个Object实例中
    let ValuePair = function (key, value) {
        this.key = key
        this.value = value
        // 重写toString方便在控制台输出结果
        this.toString = function () {
            return `${this.key}-${this.value}`
        }
    }
    
    // 重写put get 和 remove方法
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        if(!table[position]){
            table[position] = new LinkedList()
        }
        // 此时table[position]为链表，故向链表尾部添加新元素
        table[position].append(new ValuePair(key, value))
    }
    
    this.get = function (key) {
        let position = loseloseHashCode(key)
        if(table[position]) {
            let current = table[position].getHead()
            // current不是最后一个节点或者第一个节点时遍历查找键/值
            while (current.next) {
                if(current.element.key === key) {
                    return current.element.value
                }
                // 迭代current
                current = current.next
            }
            
            // current是第一个或者最后一个节点
            if(current.element.key === key) {
                return current.element.value
            }
            
        }
        return undefined
    }
    
    this.remove = function (key) {
        let position = loseloseHashCode(key)
        if (table[position]) {
            let current = table[position].getHead()
            while (current.next) {
                if(current.element.key === key) {
                    table[position].remove(current.element)
                    if(table[position].isEmpty()) {
                        table[position] = undefined
                    }
                    current = current.next
                }
            }
            
            if(current.element.key === key) {
                table[position].remove(current.element)
                // 移除元素之后判断链表是否为空，若为空则将该位置的值设为undefined
                if(table[position].isEmpty()) {
                    table[position] = undefined
                }
            }
            
            return true
        }
        return false
    }
   
}
复制代码