12.2 【HashMap】js 利用线性探查解决散列冲突问题

再次展示了js动态数组的方便性

'use strict';

// 内部类，定义链表节点内容
class valuePire {
    constructor (key, value) {
        this.key = key;
        this.value = value
    
        this.toString = function () {
            return '[ k:' + this.key + 'value: ' + this.value + ']'
        }
    } 
}
class HashMap {
    constructor () {
        this.table = []
    }
    // 散列函数
    loseloseHashCode (key) {
        let hash = 0;
        for(let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt()
        }
        return hash % 37
    }


    // 存放
    put (key, value) {
        let position = this.loseloseHashCode(key)

        if (this.table[position] === undefined) {
            this.table[position] = new valuePire(key, value)
        } else {
            let index = ++ position
            while (this.table[index] !== undefined) {
                index ++
            }
            this.table[position] = new valuePire(key, value)
        }
    }

    remove (key) {
        let position = this.loseloseHashCode(key)
        // console.log(this.table[position].key);
        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) {
                this.table[index] = undefined
            } else {
                let index = ++ position
                while (this.table[index] === undefined
                    || this.table[index].key !== key) {
                    index ++
                }
                if (this.table[index].key === key) {
                    this.table[index] = undefined
                }
            }
        }
        return undefined
    }

    get (key) {
        let position = this.loseloseHashCode(key)
        // console.log(this.table[position].key);
        if (this.table[position] !== undefined) {
            if (this.table[position].key === key) {
                return this.table[position].value
            } else {
                let index = ++ position
                while (this.table[index] === undefined
                    || this.table[index].key !== key) {
                    index ++
                }
                if (this.table[index].key === key) {
                    return this.table[index].value
                }
            }
        }
        return undefined
    }
}

let hashmap = new HashMap();
hashmap.put('Gandalf', 'gandalf@email.com')

hashmap.put('Tyrion', 'tyrion@email.com')
hashmap.put('Aaron', 'Aaron@email.com')

hashmap.put('Donnie', 'Donnie@email.com')
hashmap.put('Ana', 'Ana@email.com')

hashmap.put('Jonathan', 'Jonathan@email.com')
hashmap.put('Jamie', 'Jamie@email.com')
hashmap.put('Sue', 'Sue@email.com')
// hashmap.remove('Jamie')
let temp = hashmap.get('Jamie')
console.log(temp);