输入对话框

输出对话框

散列表(HashMap)

李艳生

湖北师范大学

物理与电子科学学院

2020年春季

回顾

  • 集合Set:元素不重复,元素=值:值
  • 字典Map:元素不重复,元素=键:值

引入

请大家思考在n个无序元素的数组中查找一个元素需要多少个操作？有没有更高性能查找的数据结构呢？

内容

散列表(重点)

散列冲突(重点)

散列函数

任务

查字典

散列表

散列表

  • 散列的作用是尽可能快地在数据结构中找到一个值
  • 数组查找值要通遍历数组查找值
  • 散列函数计算值的存储具体位置，从而快速找到值
  • 应用：数据库索引，对象存储

散列表操作

  • 创建
  • 查找
  • 添加
  • 删除
  • 转字符串

算法演示

创建散列表

  • 可用数组[]实现
  • 也可用对象{}实现

创建散列表


class HashMap {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;  //转字符串方法
        this.table = {};
    }
    put(key,value){} //添加
    remove(key){}    //移除
    get(key){}       //查找
    hashCode(key){}  //散列函数
    toString(){}     //转字符串
}
function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString(); 
}

散列函数

  • 不同的散列函数散列表性能不一样

hashCode(key) {
    if (typeof key === 'number') { 
        return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
        hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
}

添加元素

  • 该方法接收key 和value 作为参数
  • key计算散列函数值作为属性名
  • 为了保存原始键值数据，原始的key 和value同时作为属性值

添加元素


put(key, value) {
    if (key != null && value != null) {
        //const tableKey = this.toStrFn(key); 
        //this.table[tableKey] = new ValuePair(key, value); 
        const position = this.hashCode(key); 
        this.table[position] = new ValuePair(key, value);
        return true;
    }
    return false;
}
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}

删除元素

  • 要从HashMap 中移除一个值，计算散列函数找到值所在的位置
  • 如果存在，就从散列表中移除，返回true，表示元素被移除；否则返回false

删除元素


remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
        delete this.table[hash];
        return true;
    }
    return false;
}

查找元素

  • 如果元素在散列表中，返回元素值，否则返回undefined。
  • 首先要计算散列函数用来查找某个元素

get(key) {
    //const valuePair = this.table[this.toStrFn(key)]; 
    const valuePair = this.table[this.hashCode(key)];
    return valuePair == null ? undefined : valuePair.value; 
}

转字符串


toString() {
    if (this.isEmpty()) {
        return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
    objString = `${objString},{${keys[i]} => ${this.table[keys[i]].toString()}}`;
    }
    return objString;
}

散列表使用

  • 用new创建HashMap对象

const hash = new HashMap();
hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');
console.log(hash.hashCode('Gandalf') + ' - Gandalf'); //19 - Gandalf
console.log(hash.hashCode('John') + ' - John'); //29 - John
console.log(hash.hashCode('Tyrion') + ' - Tyrion');  //16 - Tyrion
console.log(hash.get('Gandalf')); // gandalf@email.com
console.log(hash.get('Loiane')); // undefined
hash.remove('Gandalf');
console.log(hash.get('Gandalf')); //undefined

散列表使用

问题

  • 请大家发现下面代码有没有什么问题？

const hash = new HashMap();
hash.put('Ygritte', 'ygritte@email.com');
hash.put('Jonathan', 'jonathan@email.com');
hash.put('Jamie', 'jamie@email.com');
hash.put('Jack', 'jack@email.com');
console.log(hash.hashCode('Ygritte') + ' - Ygritte');       //4 - Ygritte 
console.log(hash.hashCode('Jonathan') + ' - Jonathan');     //5 - Jonathan 
console.log(hash.hashCode('Jamie') + ' - Jamie');           //5 - Jamie 
console.log(hash.hashCode('Jack') + ' - Jack');             //7 - Jack

散列冲突

  • 一些键会有相同的散列代码
  • 不同的值在散列表中对应相同位置

处理冲突

  • 拉链法
  • 线性探测法
  • 二次探测法
  • 再散列法

拉链法

  • 为散列表的每一个位置创建一个链表并将元素存储在里面

创建散列表


class HashMapWithChaining {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;  //转字符串方法
        this.table = {};
    }
    put(key,value){} //添加
    remove(key){}    //移除
    get(key){}       //查找
    hashCode(key){}  //散列函数
}
function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString(); 
}

添加元素


put(key, value) {
    if (key != null && value != null) {
        const position = this.hashCode(key); 
        if (this.table[position] == null) {
            this.table[position] = new LinkedList();
        }
        this.table[position].push(new ValuePair(key, value));
        return true;
    }
    return false;
}
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}

查找元素


get(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position]; 
    if (linkedList != null && !linkedList.isEmpty()) {
    let current = linkedList.head; 
    while (current != null) { 
        if (current.element.key === key) { 
            return current.element.value; 
        }
        current = current.next; 
    }
    }
    return undefined; 
}

删除元素


remove(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !linkedList.isEmpty()) {
        let current = linkedList.head;
        while (current != null) {
            if (current.element.key === key) { 
                linkedList.remove(current.element); 
                if (linkedList.isEmpty()) { 
                    delete this.table[position]; 
                }
                return true; 
            }
            current = current.next; 
        }
    }
    return false;
}

线性探测法

  • 向表中某个位置添加一个新元素时，如果索引为position 的位置已经被占据，依次尝试position+1,position+2,...，直到找到空位置

创建散列表


class HashMapWithLinear {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;  //转字符串方法
        this.table = {};
    }
    put(key,value){} //添加
    remove(key){}    //移除
    get(key){}       //查找
    hashCode(key){}  //散列函数
}
function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString(); 
}

添加元素


put(key, value) {
    if (key != null && value != null) {
        const position = this.hashCode(key);
        if (this.table[position] == null) { 
            this.table[position] = new ValuePair(key, value); 
        } else {
            let index = position + 1; 
            while (this.table[index] != null) { 
                index++; 
            }
            this.table[index] = new ValuePair(key, value); 
        }
        return true;
    }
    return false;
}
class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString() {
        return `[#${this.key}: ${this.value}]`;
    }
}

查找元素


get(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) { 
        if (this.table[position].key === key) { 
            return this.table[position].value; 
        }
        let index = position + 1; 
        while (this.table[index] != null && this.table[index].key !== key) { 
            index++;
        }
        if (this.table[index] != null && this.table[index].key === key) { 
            return this.table[position].value; 
        }
    }
    return undefined; 
}

删除元素


软删除

删除元素


硬删除

删除元素


remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
        if (this.table[position].key === key) {
            delete this.table[position]; 
            this.verifyRemoveSideEffect(key, position); 
            return true;
        }
        let index = position + 1;
        while (this.table[index] != null && this.table[index].key !== key ) {
            index++;
        }
        if (this.table[index] != null && this.table[index].key === key) {
            delete this.table[index]; 
            this.verifyRemoveSideEffect(key, index); 
            return true;
        }
    }
    return false;
}
verifyRemoveSideEffect(key, removedPosition) {
    const hash = this.hashCode(key); 
    let index = removedPosition + 1; 
    while (this.table[index] != null) { 
        const posHash = this.hashCode(this.table[index].key); 
        if (posHash <= hash || posHash <= removedPosition) { 
            this.table[removedPosition] = this.table[index];
            delete this.table[index];
            removedPosition = index;
        }
        index++;
    }
}

散列函数

  • 直接定址法
  • 除留余数法
  • 随机数法
## 直接定址法 $$ hashCode(key) = key $$ $$ hashCode(key) = a * key + b $$
## 除留余数法 $$ hashCode(key) = key \\% p $$ (p<=m,m为散列表长)
## 随机数法 $$ hashCode(key) = random(key) $$ (random为随机函数)

散列函数


hashCode(key) {
    const tableKey = this.toStrFn(key); 
    let hash = 5381;
    for (let i = 0; i < tableKey.length; i++) { 
        hash = (hash * 33) + tableKey.charCodeAt(i); 
    }
    return hash % 1013;
}
## 装填因子 $$ \alpha = \frac {表中填入的元数个数} {表长} $$

性能

  • 散列函数
  • 处理散列冲突方法
  • 装填因子
## 性能 |散列冲突|查找成功|查找不成功| |:-------|:------:|:--------:| |线性探测法|$ \frac{1}{2}(1 + \frac{1}{1-\alpha}) $|$ \frac{1}{2}(1 + \frac{1}{(1-\alpha)^2}) $| |拉链法| $ 1+ \frac {\alpha}{2} $ | $ \alpha + e^{-\alpha} $ |
## 比较 #### 平均情况时间复杂度 |数据结构|访问|查找|添加|删除| |:--|:--:|:--:|:--:|:--:| |数组|O(1)|O(n)|O(n)|O(n)| |链表|O(n)|O(n)|O(1)|O(1)| |散列表|N/A|O(1)|O(1)|O(1)|
## 比较 #### 最坏情况时间复杂度 |数据结构|访问|查找|添加|删除| |:--|:--:|:--:|:--:|:--:| |数组|O(1)|O(n)|O(n)|O(n)| |链表|O(n)|O(n)|O(1)|O(1)| |散列表|N/A|O(n)|O(n)|O(n)|

任务

分别向数组和散列表中存放1至100000共10万个元素，比较两种数据结构查找99999的性能。