数据结构——散列

2018-02-21 本文已影响0人柏丘君

散列也叫作散列表，是一种非线性的数据结构，可以用来快速的查找和插入数据。在 JavaScript 中，通常使用数组来实现散列。
散列的核心是一个计算特征值的方法，该方法将原始数据进行转换，返回一个索引，随后将值保存在数组对应的索引中。此外，该方法还可以用来进行高效的查找。
由于不同的特征值计算出的索引不尽相同，因此散列在保存数据时不是按顺序保存的，其是基于列表这样一个线性结构上的“非线性”结构，因此被称为散列。
通常，我们会将数组的长度设置为一个质数，因为质数的公约数最少，可以有效的防止碰撞。

散列的代码实现

下面是 IHashTable 的接口定义：

interface IHashTable<T>{
    // 获取索引值
    getIndex(flag:string):number;
    // 两种存放方式：放入值，放入一个值和简称值
    put(flag:string,ele:T):void;
    // 获取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 获取散列中的元素
    toString():T[];    
}

上面的 IHashTable 中定义了一个 put 方法，该方法用来向散列中添加元素。其第一个参数是要添加元素的一个别名，第二个参数是元素本身。如：

hashTable.put("MIKE","mike@mike.com")
hashTable.put("JACK","jack@jack.com")

下面是 HashTable 的代码实现：

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:T[] = [];
    // 散列表的长度
    private dataStoreLen:number = 0;
    // 盐值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 创建散列对象时传入散列表的长度和盐值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置为计算出的 hash 值对数组的长度取余
        return pos;
    }
    put(flag:string,ele:T):void{
        const pos:number = this.getIndex(flag);
        this.dataStore[pos] = ele;
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        return this.dataStore[pos];
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const res = this.dataStore[pos];        
        this.dataStore[pos] = undefined;
        return res;
    }
    toString():T[]{
        const tmp:T[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

简单测试一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
// 获取元素
console.log(h.get("PENNY"))
console.log(h.toString())
// 移除元素
h.remove("JERRY")
console.log(h.toString())

运行结果：

penny@penny.com
[ 'penny@penny.com',
  'jerry@jerry.com',
  'jack@jack.com',
  'mike@mike.com' ]
[ 'penny@penny.com', 'jack@jack.com', 'mike@mike.com' ]

碰撞问题

散列的碰撞也叫作散列的冲突，是指不同的别名计算出了相同的索引，上面代码中实现的 getIndex() 方法，使用字符串的 charCodeAt() 方法获取所有字符的 ASCII 码，并将这些 ASCII 码值相加，得到一个数值，然后使用这个数值对散列表的长度取余，就得到了元素在散列表中的位置。
但只进行上述简单的计算，是非常容易产生冲突的，譬如下面的测试代码：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
h.put("ACKJ","ackj@ackj.com")
console.log(h.toString())

运行结果：

[ 'penny@penny.com',
  'jerry@jerry.com',
  'ackj@ackj.com',
  'mike@mike.com' ]

从上面的运行结果中可见，最先插入的 jack@jack.com 被后插入的 ackj@ackj.com 给覆盖了，这是因为在使用 getIndex() 方法对 JACK 和 ACKJ 计算索引值时，得到了相同的结果，导致后面插入的元素覆盖了前面的元素。
要解决这个问题，首先可以优化 getIndex() 方法：

...
getIndex(flag:string):number{
    // 减少散列碰撞，加点盐
    let 
        hash:number = -1,
        pos:number = -1;

    if(flag.length){
        hash = 0;
        for(const c of flag){
            hash += (this.hashSalt * hash + c.charCodeAt(0));
        }
        pos = hash % this.dataStoreLen;
    }
    // 存放位置为计算出的 hash 值对数组的长度取余
    return pos;
}
...

再次执行上面的测试代码，运行结果如下：

[ 'penny@penny.com',
  'mike@mike.com',
  'jerry@jerry.com',
  'jack@jack.com',
  'ackj@ackj.com' ]

通过对 getIndex() 做一些修正，解决了 JACK 和 ACKJ 的冲突。
下面再推荐一个更好的散列函数：djb2 函数。

...
getIndex(flag:string):number{
    let hash:number = 5381;
    for (const c of flag) {
        hash = hash * 33 + c.charCodeAt(0);
    }
    return hash % 1013;
}
...

使用这个函数时，要求散列表的长度大于 1013，因此还需要对类的代码进行一些改进，这里就不再详述了。

解决碰撞的其他方案

上面对获取索引值的 getIndex() 方法做了一些修改，以达到解决冲突的目的。除此之外，解决散列冲突还有两个常用的方案：分离链接法（开链法）和线性探测法。将这两个方案和上面 getIndex() 方法进行结合，解决碰撞会更加有效。下面依次介绍这两个方案。

分离链接法

分离链接法也叫开链法，是解决散列碰撞的一种常用方法。在前面实现的 HashTable 类中，散列表在每个索引处存放的是一个元素，应用开链法时，散列表在买个索引处存放的不再是一个具体的元素，而是一个列表，碰撞的元素通通存放在这个列表中。以前面 JACK 和 ACKJ 的碰撞为例，应用分离链接法时，它们在散列表中的是这样存放的：

[
  {key:"JACK",value:"jack@jack.com"},
  {key:"ACKJ",value:"ackj@ackj.com"}
]

在查找或移除元素时，会遍历这个列表，根据某个 KEY 值，找到相应的元素。
对于列表，如果想综合应用前面的知识，可以采用 List 或者链表，甚至集合实现都可以。方法有很多，不用只局限于 JavaScript 数组这一种数据结构，可以根据前面介绍的那些数据结构进行灵活组合。我这里就采用 ES6 原生的 Map 集合。同时，为了方便观察效果，我将 getIndex() 修改回原始的定义，在实际应用中，最好将其换成 djb2 函数。下面是经过改进的 IHashTable 接口和 HashTable 类：

interface IHashTable<T>{
    // 获取索引值
    getIndex(flag:string):number;
    // 两种存放方式：放入值，放入一个值和简称值
    put(flag:string,ele:T):void;
    // 获取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 获取散列中的元素
    toString():Map<string,T>[];    
}

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:Map<string,T>[] = [];
    // 散列表的长度
    private dataStoreLen:number = 0;
    // 盐值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 创建散列对象时传入散列表的长度和盐值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        // let hash:number = 5381;
        // for (const c of flag) {
        //     hash = hash * 33 + c.charCodeAt(0);
        // }
        // return hash % 1013;
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置为计算出的 hash 值对数组的长度取余
        return pos;
    }
    put(flag:string,ele:T):void{
        const pos:number = this.getIndex(flag);
        // 初始化操作
        if(this.dataStore[pos] === undefined){
            // 创建一个 Map 对象
            const tmp = new Map<string,T>();
            tmp.set(flag,ele);
            this.dataStore[pos] = tmp;
        }else{
            this.dataStore[pos].set(flag,ele);
        }
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        return this.dataStore[pos].get(flag);
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const res = this.get(flag);        
        this.dataStore[pos].delete(flag);
        return res;
    }
    toString():Map<string,T>[]{
        const tmp:Map<string,T>[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

测试一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("PENNY","penny@penny.com")
h.put("JERRY","jerry@jerry.com")
h.put("ACKJ","ackj@ackj.com")
console.log(h.toString())

运行结果：

[ Map { 'PENNY' => 'penny@penny.com' },
  Map { 'JERRY' => 'jerry@jerry.com' },
  Map { 'JACK' => 'jack@jack.com', 'ACKJ' => 'ackj@ackj.com' },
  Map { 'MIKE' => 'mike@mike.com' } ]

线性探测法

线性探测法是解决散列冲突的另一种常用手段，在使用 put() 方法向散列中插入元素时，如果发现产生了碰撞，就从获取的索引处依次向下查找，直到找到空位，将元素插入。
下面是使用改进后的 IHashTable 接口和 HashTable 类的实现：

interface IHashTable<T>{
    // 获取索引值
    getIndex(flag:string):number;
    // 两种存放方式：放入值，放入一个值和简称值
    put(flag:string,ele:T):void;
    // 获取值
    get(flag:string):T;
    // 移除元素
    remove(flag:string):T;
    // 查找元素
    find(flag:string,startPos:number):number;
    // 获取散列中的元素
    toString():{key:string,value:T}[];    
}

class HashTable<T> implements IHashTable<T>{
    // 散列表
    private dataStore:{key:string,value:T}[] = [];
    // 散列表的长度
    private dataStoreLen:number = 0;
    // 盐值
    private hashSalt:number = 71;
    constructor(dataStoreLen:number,hashSalt?:number){
        // 创建散列对象时传入散列表的长度和盐值
        this.dataStoreLen = dataStoreLen;
        if(hashSalt){
            this.hashSalt = hashSalt;
        }
    }
    getIndex(flag:string):number{
        // let hash:number = 5381;
        // for (const c of flag) {
        //     hash = hash * 33 + c.charCodeAt(0);
        // }
        // return hash % 1013;
        let hash:number = -1,pos:number = -1;
        if(flag.length){
          hash = 0;
          for(const c of flag){
              hash += c.charCodeAt(0);
          }
          pos = hash % this.dataStoreLen;
        }
        // 存放位置为计算出的 hash 值对数组的长度取余
        return pos;
    }
    find(flag:string,startPos:number):number{
        let len:number = this.dataStoreLen;
        while(len--){
            const tmp = this.dataStore[startPos];
            if(tmp.key === flag){
                return startPos;
            }
            startPos++;
        }
    }    
    put(flag:string,ele:T):void{
        let pos:number = this.getIndex(flag);
        // 初始化操作
        if(this.dataStore[pos] === undefined){
            const tmp = {key:flag,value:ele};
            this.dataStore[pos] = tmp;
        }else{
            const tmp = {key:flag,value:ele};
            while(this.dataStore[pos] !== undefined){
                pos++;
            }            
            this.dataStore[pos] = tmp;
        }
    }
    get(flag:string):T{
        const pos:number = this.getIndex(flag);
        const realPos:number = this.find(flag,pos);
        return this.dataStore[realPos].value;
    }
    remove(flag:string):T{
        const pos:number = this.getIndex(flag);
        const realPos:number = this.find(flag,pos);
        const res = this.get(flag);        
        this.dataStore[realPos] = undefined;
        return res;
    }
    toString():{key:string,value:T}[]{
        const tmp:{key:string,value:T}[] = [];
        for(const ele of this.dataStore){
            if(ele !== undefined){
                tmp.push(ele);
            }
        }
        return tmp;
    }
}

测试一下：

const h = new HashTable<string>(301);
h.put("MIKE","mike@mike.com")
h.put("JACK","jack@jack.com")
h.put("ACKJ","ackj@ackj.com")
h.put("PENNY","penny@penny.com")
h.put("CKAJ","ckaj@ckaj.com")
h.put("AKCJ","ackj@ackj.com")
h.put("JERRY","jerry@jerry.com")
console.log(h.toString())

运行结果：

[ { key: 'PENNY', value: 'penny@penny.com' },
  { key: 'JERRY', value: 'jerry@jerry.com' },
  { key: 'JACK', value: 'jack@jack.com' },
  { key: 'ACKJ', value: 'ackj@ackj.com' },
  { key: 'CKAJ', value: 'ckaj@ckaj.com' },
  { key: 'AKCJ', value: 'ackj@ackj.com' },
  { key: 'MIKE', value: 'mike@mike.com' } ]

至此，我们使用线性探测法解决了散列的碰撞问题，使用线性探测法解决碰撞问题时，散列表需要足够的长度。

总结

本文介绍了散列这种数据结构，散列是一种非线性的，可以快速查找和插入数据的数据结构，散列的核心是一个计算特征值的方法。在计算特征值时，容易产生冲突，要解决冲突可以从以下三个方面进行：

优化计算特征值的方法，推荐使用 djb2 函数
使用分离链接法，也称作开链法解决冲突
使用线性探测法解决冲突

将这几个方法进行结合使用，可以达到更好的效果。

完。

数据结构——散列

散列的代码实现

碰撞问题

解决碰撞的其他方案

分离链接法

线性探测法

总结

猜你喜欢

热点阅读