散列表的冲突解决

[xszi]

不同的值在散列表中对应相同位置，会导致数据的覆盖丢失，即为冲突。

1. 分离链接

function HashTable() {
    var table = []

    var loseloseHashCode = function(key) {
        var hash = 0
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        return hash % 37
    }

    // 增加一个辅助类
    var ValuePair = function(key, value) {
        this.key = key
        this.value = value

        this.toString = function () {
            return '[' + this.key + ' - ' + this.value + ']'
        }
    }

    this.put = function(key, value) {
        var position = loseloseHashCode(key)

        if (table[position] == undefined) {
            // 使用链表
            table[position] = new linkedList()
        }

        table[position.append(new ValuePair(key, value))]
    }

    this.get = function (key) {
        var position = loseloseHashCode(key)

        if (table[position] !== undefined) {

            // 遍历链表来寻找键 / 值
            var current = table[position].getHead()
            while (current.next) {
                if (current.element.key === key) {
                    return current.element.value
                }
                current = current.next
            }
        }

        // 检查元素在链表第一个或最后一个节点的情况
        if (current.element.key === key) {
            return current.element.value
        }

        return undefined
    }

    this.remove = function(key) {

        var position = loseloseHashCode(key)

        if (table[position] !== undefined) {

            var current = table[position].getHead()
            while (current.next) {
                if (current.element.key === key) {
                    table[position].remove(current.element)
                    if (table[position].isEmpty()) {
                        table[position] = undefined
                    }
                    return true
                }
                current = current.next
            }
        }

        // 检查是否为第一个或最后一个元素
        if (current.element.key === key) {
            table[position].remove(current.element)
            if (table[position].isEmpty()) {
                table[position] = undefined
            }
            return true
        }

        return false
    }
}

2. 线性探查

注意：

在一些编程语言中，我们需要定义数组的大小。如果使用线性探查的话，需要注意的一个问题是数组的可用位置可能会被用完。在JavaScript中，我们不需要担心这个问题，因为我们不需要定义数组的大小，它可以根据需要自动改变大小。（JS的内置功能）

function HashTable() {
    var table = []

    var loseloseHashCode = function(key) {
        var hash = 0
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        return hash % 37
    }

    // 增加一个辅助类
    var ValuePair = function(key, value) {
        this.key = key
        this.value = value

        this.toString = function () {
            return '[' + this.key + ' - ' + this.value + ']'
        }
    }

    this.put = function(key, value) {
        var position = loseloseHashCode(key)
        // 使用线性查找
        if (table[position] === undefined) {
           table[position] = new ValuePair(key, value) 
        } else {
            var index = ++position
            while (table[index] !== undefined) {
                index++
            }
            table[index] = new ValuePair(key, value)
        }
    }

    this.get = function (key) {
        var position = loseloseHashCode(key)

        if (table[position] !== undefined) {
            if (table[position].key === key) {
                return table[position].value
            } else {
                var index = ++position
                while (table[index] === undefined || table[index].key !== key) {
                    index++
                }
                if (table[index].key === key) {
                    return table[index].value
                }
            }
        }
        return undefined
    }

    this.remove = function(key) {

        var position = loseloseHashCode(key)

        if (table[position] !== undefined) {
            if (table[position].key === key) {
                table[position].value = undefined
                return true
            } else {
                var index = ++position
                while (table[index] === undefined || table[index].key !== key) {
                    index++
                }
                if (table[index].key === key) {
                    table[index].value = undefined
                    return true
                }
            }
        }
        return false
    }
}

3. 创建更好的散列函数（没有最好，只有更好）

// 社区推崇
var djb2HashCode = function(key) {
    var hash = 5381
    for (var i = 0; i < key.length; i++) {
        hash = hash * 33 + key.charCodeAt(i)
    }

    return hash % 1013
}