数据结构 | 哈希表

哈希表基础知识

哈希表，又叫散列表（HashTable或者HashMap），是根据键直接访问记录在存储位置的数据结构，通过哈希函数根据计算出在哈希表中的内存地址

作用是尽可能快地在数据结构中找到一个值

实现哈希表

实现方法

• get(val)
• put(key, val)
• remove(key)

手写实现

class ValuePair {
    constructor(key, val) {
        this.key = key;
        this.val = val;
    };
    
    toString() {
        return `[${this.key}:${this.val}]`;
    }
}

class HashTable {
    constructor(toStrFn) {
        this.table = {};
    }
    
    
    // 1. 创建哈希函数: 传入key -> 获取内存地址
    loseloseHashTable(key) {
        if (typeof key === 'number') {
            return key;
        }
        
        const tablekey = String(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++) {
            hash += tablekey.charCodeAt(i);
        }
        return hash % 37;  // 获取hash值
    }
    
    hashCode(key) {
        return this.loseloseHashTable(key);
    }
    
    // hashTable添加键值对
    put(key, val) {
        if (key !== null && val !== null) {
            const position = this.hashCode(key);   // position是内存地址
            this.table[position] = new ValuePair(key, val);
            return true;
        }
        return false;
    }
    
    // hashTable中获取val
    get(key) {
        const valuePair = this.table[this.hashCode(key)];
        return valuePair = valuePair ? valuePair.val : undefined;
    }
    
    
    // hashTable删除值
    remove(key) {
        const hash = this.hashCode(key);
        const valuePair = this.table[hash];
        if (valuePair) {
            // 使用delete或者设置null或者undefined是一样的
            delete this.table[hash];
            return true;
        }
        return false;
    }
}

测试一下子~

const hash = new HashTable();

hash.put('Katrina', '111.com');
hash.put('Jenny', '222.com');
hash.puth('Kate', '333.com');

console.log(hash.hashCode('Katrina') + '-Katrina');
console.log(hash.hashCode('Jenny') + '-Jenny');
console.log(hash.hashCode('Kate') + '-Kate');

/*
	11-Katrina
	35-Jenny
	19-Kate
*/

console.log(hash.get('Katrina'));   // 111.com
console.log(hash.get('Lisa'));    // undefined

hash.remove('Kate');
console.log(hash.get('Kate'));   // undefined

哈希表和哈希集合

处理哈希表中的冲突

一些键会有相同的hash值，比如hash.hashCode('Jenny')和hash.hashCode('Jisoo')都是35，一般来说，具有相同hash值的数据在hash表中值会被替换

看下面的代码：

const hash = new HashTable();

hash.put('Jisoo', '111.com');
hash.put('Jenny', '222.com');

console.log(hash.hashCode('Jisoo') + '-Jisoo');   // 35-Jisoo
console.log(hash.hashCode('Jenny') + '-Jenny');   // 35-Jenny

console.log(hash.get('Jisoo'));   // 222.com  显然已经被替换

处理冲突的方法有：分离链接、线性探查、双散列法

1. 分离链接

分离链接指的是为哈希表的每一个位置创建一个链表并且要将元素存储在里面

• 重写put方法

  重写思路：验证要加入的新元素的位置是否已经被占据，如果已经占据，会创建一个NodeList实例，将ValuePair加入到这个实例

• 重写get

  重写思路：验证能否在特定位置找到该元素，定位后，通过遍历ListNode得到元素，没有找到就返回undefined

• 重写remove

  重写思路：类似于定位后找到链表，然后去删除链表中的节点

2. 线性探查

将元素直接存到表中，而不是在单独的数据结构中

• 重写put

  重写思路：当向hash表存放元素的时候，若发现position已经被占据了，就存放在position+1中，如果position+1也被占据了，则存放在position+2中，以此类推…

• 重写get

  重写思路：查找键，不存在一定是undefined，如果存在就要检查我们要找的值是不是在这个原始位置上，如果不是，就继续找，完整迭代后还是找不到返回undefined

• 重写remove

​ 重写思路和put基本相同，不再赘述

3. 双散列法

创建更好地散列函数：1. 插入和检索元素的时间；2. 较低的冲突可能性

比lose lose哈希函数更好的函数是djb2

djb2HashCode(key) {
    const tableKey = String(key);
   	let hash = 5381;  // 初始化一个hash变量并且赋值
    for (let i = 0; i < table.length; i++) {
        hash = (hash * 33) + tableKey.charCodeAt(i);
    }
    return hash % 1013;
}

参考

代码随想录_哈希表