数据结构-散列

摘要：散列是一种常用的数据存储技术散列后的数据可以快速的插入或取用散列使用的数据结构叫做散列表在散列表上插入删除和取用的数据都非常快但是对于查找操作来说却效率低下比如查找一组数据中最大值和最小值这些操作得求助于其它数据结构二叉查找树就是一个很好的

散列是一种常用的数据存储技术, 散列后的数据可以快速的插入或取用. 散列使用的数据结构叫做 散列表 . 在散列表上插入、删除和取用的数据都非常快, 但是对于查找操作来说却效率低下, 比如查找一组数据中最大值和最小值. 这些操作得求助于其它数据结构, 二叉查找树就是一个很好的选择. 本章介绍如何实现散列, 以及了解什么时候应用散列存取数据.

我们的散列表示基于数组进行设计的. 数组的长度是预先设定的, 如有需要, 可以随时增加. 所有元素根据和该元素对应的键, 保存在数组的特定位置, 该键和我们前面讲到的字典中的键是类似的概念. 使用散列表存储数据时, 通过一个散列函数将键映射为一个数字, 这个数字的范围是0到散列表的长度.

理想情况下, 散列函数会将每个键映射为一个唯一的函数索引. 然鹅, 键的数量是无限的, 数组的长度是有限的(理论上, 在js中是这样的). 一个更现实的目标是让散列函数尽量将键均匀地映射到数组中.

即使使用一个搞笑的散列函数, 仍然存在将两个键映射成同一个值的可能, 这样现象称为 碰撞(collision) , 当 碰撞 发生时, 我们需要有方法去解决. 本章稍后将详细讨论如何解决 _碰撞_.

要确定的最后一个问题是: 散列表中的数组究竟应该有多大? 这是编写散列函数时必须要考虑的. 对数组大小常见的限制是: 数组长度应该是一个质数. 在实现各种散列函数时, 我们将讨论为什么要求数组长度为质数. 之后, 会有多种确定数组大小的策略, 所有的策略都基于处理碰撞的技术, 因此, 我们将讨论如何处理碰撞时对它们进行讨论.

我们使用一个类来表示散列表, 该类包含计算散列值的方法、向散列中插入数据的方法、从散列表中读取数据的方法、显示散列表中数据分布的方法, 以及其它一些可能会用到的工具方法.

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash() {

    }
    showDistro() {

    }
    put() {
        
    }
}

散列函数的选择依赖于键值的数据类型. 如何键是整型, 最简单的散列函数就是以数组的长度对键取余. 在一些情况下, 比如数组的长度是10, 而键值都是10的倍数时, 就不推荐使用这种方式了. 这也是数据长度为什么要是质数的原因之一, 就像我们在上个构造函数中, 设定数组长度为137一样. 如何键是随机的整数, 则散列函数应该更均匀地分布这些键. 这种散列方式称为: 除留余数法 .

在很多应用中, 键是字符串类型. 事实证明, 选择针对字符串类型的散列函数是很难的, 选择时必须加倍小心.

乍一看, 将字符串中的每个字符的ASCII码值相加似乎是一个不错的散列函数. 这样散列值就是ASCII码值的和 除以数组长度的余数. 该散列的方法_simpleHash():

...
_simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
...

再给HashTable加两个方法: put()和_showDistro(), 一个用来将数据存入散列表, 一个用来显示散列表中的数据, 这样就初步实现了HashTable类.

...
showDistro() {
    this._table.forEach((i, index) => {
        if(i != undefined) {
            log(`${index}: ${i}`)
        }
    })
}
put(data) {
    const pos = this._simpleHash(data);
    this._table[pos] = data;
}
...

做一个简单散列:

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(data) {
        const pos = this._simpleHash(data);
        this._table[pos] = data;
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
someNames.forEach(i => {
    h.put(i);
});
h.showDistro();

输出如下:

35: Cynthia
45: Clayton
57: Donnie
77: David
95: Danny
116: Mike
132: Jennifer
134: Jonathan

_simpleHash()函数通过使用JS的charCodeAt()函数, 返回每个字符的ASCII码值, 然后再将它们相加得到散列值. put()方法通过调用_simpleHash()函数得到数组的索引, 然后将数据存储到该索引对应的位置上. 你会发现, 数据并不是均匀分布的, 人名想数组的两端集中.

比起这种不均匀的分布, 还有一个更严重的问题. 如果你仔细观察输出, 会发现初始的数组中的人名并没有全部显示. 给_simpleHash()函数加入一条console.log()输出,
log("Hash value:" + data + "->" + total);
运行程序你就会发现有两个字符串"Clayton"和"Raymond"的散列值是一样的. 一样的散列值引发了碰撞, 因为碰撞, 只有"Clayton"存入了散列表. 可以通过改善散列函数来避免碰撞.

为了避免碰撞, 首先要确保散列表中用来存储数据的数组其大小是个 质数. 这一点很关键, 这和计算散列值时使用的取余运算有关. 数组的长度应该在100以上, 这是为了让数据在散列表中分布得更加均匀. 通过试验我们发现, 比100大且不会让数据产生碰撞的第一个质数是137. 使用其它更接近100的质数, 在该数据集上依然会产生碰撞.

为了避免碰撞, 在给散列表一个合适的大小后, 接下来要有一个计算散列值的更好方法.
霍纳算法 很好的解决了这个问题. 本书不会过深入该算法的数学细节, 在此算法中, 新的散列函数仍然先计算字符串中各字符的ASCII码值, 不过求和时每次要乘以一个质数. 大多数算法书建议使用一个较小的质数, 比如31, 但是对于我们的数据集, 31不起作用, 我们使用37, 这样刚好不会产生碰撞.

_betterHash(data) {
    const H = 37;
    let total = 0;
    for(let i = 0; i < data.length; i++) {
        total += H * total + data.charCodeAt(i);
    };
    total = total % this._table.length;
    if(total < 0) {
        total += this._table.length - 1;
    };
    
    return parseInt(total);
}

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(data) {
        const pos = this._betterHash(data);
        this._table[pos] = data;
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
someNames.forEach(i => {
    h.put(i);
});
h.showDistro();

程序输出:

12: Jennifer
22: Raymond
55: Donnie
58: Clayton
80: Jonathan
82: Mike
103: Cynthia
110: Danny

这次所有的人名都显示出来了, 而且没有碰撞.

上面展示了如何散列化字符串类型的键, 接下来介绍如何使用散列化整型键, 使用的数据集是学生的成绩. 我们将随机产生一个9位数的键, 用以识别学生身份和一门成绩. 下面是产生学生数据(包含ID和成绩)的函数:

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1) + min);
};

function genStuData(arr) {
    for(let i = 0; i < arr.length; i++) {
        let num = "";
        for(let j = 1; j <= 9; j++) {
            num += Math.floor(Math.random() * 10)
        };
        num += getRandomInt(50, 100);
        arr[i] = num;
    };
};

使用getRandomInt()函数时, 可以指定随机数的最大值和最小值. 拿学生成绩来说, 最低分50, 最高分100.

genStuData()函数生成学生的数据. 里层的循环用来生成学生的ID, 紧跟在循环后面的代码生成一个随机的成绩, 并把成绩缀在ID的后面. 主程序会把ID和成绩分离. 散列函数将学生ID里的数字相加, 使用_simpleHash()函数计算出散列值.

执行程序:

const students = new Array(10);
genStuData(students);
students.forEach(i => {
    log(i.substring(0, 8) + "  " + i.substring(9))
});

const h = new HashTable();
students.forEach(i => {
    h.put(i)
});
h.showDistro();

程序输出:

83700897  87
25732026  56
60875817  85
49919842  77
09796486  57
67922868  58
57820350  58
70903358  54
46307166  100
09033369  99
23: 57820350058
25: 70903358154
27: 25732026956
38: 09033369799
41: 49919842177
46: 09796486557
49: 67922868858
62: 463071660100

散列函数再一次发生碰撞, 数组中没有包含所有的数据. 事实上, 如果将程序多跑几次, 有时会出现正常的情况, 但是结果太不一致了. 可以通过修改数组的大小, 或者在调用put()方法时使用更好的_betterHash()函数, 来试试能不能解决碰撞.
使用_betterHash()散列函数得到的输出:

88200007  99
22314764  82
25636690  64
88623060  53
17940629  70
59142776  58
14774034  70
90261540  66
02406002  75
95463920  65
8: 59142776758
27: 22314764782
46: 95463920165
57: 25636690564
78: 90261540066
80: 88623060453
98: 17940629670
108: 14774034770
112: 02406002475
114: 88200007799

很明显: 无论是字符串还是整型, _betterHash()的散列效果都更胜一筹.

前面讲的是散列函数, 现在学以致用, 看看如何使用散列表来存储数据. 为此, 需要修改put()方法, 使得该方法同时接受键和数据作为参数, 对键值散列后, 将数据存储到散列表中.

然后定义get()方法, 用以读取存储在散列表中的数据. 该方法同样需要对键值进行散列化, 然后才能知道数据到底存储在数组的什么位置.

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i != undefined) {
                log(`${index}: ${i}`)
            }
        })
    }
    put(key, data) {
        const pos = this._betterHash(key);
        this._table[pos] = data;
    }
    get(key) {
        return this._table[this._betterHash(key)];
    }
};

const h = new HashTable();
h.put("张三", 110);
h.put("李四", 112);
h.put("王五", 119);

log(h.get("王五")); // 输出 119

当散列函数对于多个输入产生同样的输出时, 就产生了碰撞. 散列算法的第二部分就是介绍如何解决碰撞, 是所有键都得以存储在散列表中. 下面介绍两种解决办法: 开链法 和 线性探测法 .

当碰撞发生时, 我们仍希望将键存储到通过散列算法产生的索引位置上, 但实际上, 不可能将多份数据存储到一个数组单元中. 开链法是指实现散列列表的底层数组中, 每个数组元素又是一个新的数据结构, 比如另一个数组, 这样就能存储多个键了.
使用这种技术. 即使两个键散列后的值相同, 依然被保存在同样的位置, 只不过它们在第二个数组中的位置不一样罢了.

实现开链法的方法时: 在创建存储散列过的键值的数组时, 通过调用一个函数创建一个新的空数组, 然后将该数组赋给散列表里的每个数组元素. 这样就创建了一个二维数组. 我们定义了一个函数buildChains()函数用来创建第二组数组, 我们也称这个数组为 链 .
完整代码:

window.log = console.log.bind(console)

class HashTable {
    constructor() {
        this._table = new Array(137);
    }
    _simpleHash(data) {
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };

        return total % this._table.length;
    }
    _betterHash(data) {
        const H = 37;
        let total = 0;
        for(let i = 0; i < data.length; i++) {
            total += H * total + data.charCodeAt(i);
        };
        total = total % this._table.length;
        if(total < 0) {
            total += this._table.length - 1;
        };
        
        return parseInt(total);
    }
    showDistro() {
        this._table.forEach((i, index) => {
            if(i[0] != undefined) {
                log(`${index}: ${i}`)
            }
        });
    }
    buildChains() {
        for(let i = 0; i < this._table.length; i++) {
            this._table[i] = new Array();
        };
    }
    put(key, data) {
        const pos = this._betterHash(key);

        let index = 0;
        if(this._table[pos][index] == undefined) {
            this._table[pos][index] = data;
        } else {
            while(this._table[pos][index] != undefined) {
                ++index
            };
            this._table[pos][index] = data;
        }
    }
    get(key) {
        let index = 0;
        const pos = this._betterHash(key);
        
        while ((this._table[pos][index] != undefined) && (this._table[pos][index] != key)) {
            index += 1;
        };
        if(this._table[pos][index] == key) {
            return this._table[pos][index];
        } else {
            return undefined;
        }
    }
};

const someNames = [ "David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan" ];
const h = new HashTable();
h.buildChains();
someNames.forEach(i => {
    h.put(i, i);
});
h.showDistro();

log(h.get("David"))
log(h.get("Jonathan"))

考虑到散列表现在使用多维数组存储数据, 为了更好地显示使用了开链法后键值的分布, 修改了showDistor()方法.

重新定义了put(), 将键值散列, 散列后的的值对应数组中的一个位置, 先尝试将数据放在该位置上的数组中的第一个单元格, 如果该单元格已经有数据了, put()方法会搜索下一个位置, 知道找到能放置数据的单元格, 并把数据存储进去. 这里实际上可以用this._table[pos].push(data)来代替, 因为通过buildChains()方法已经将散列表中的元素修改为二维数组(链).

get()方法先对键值散列, 根据散列后的值找到散列表中相应的位置, 然后搜索该位置上的链, 知道找到键值. 如果找到, 就将紧跟在键值后面的数据返回; 如果没有, 就返回undefined.

第二种处理碰撞的方法是 线性探测法 . 线性探测法隶属于一种更一般化的散列技术: _开放寻址散列_. 当发生碰撞时, 线性探测法检查散列表中的下一个位置是否为空. 如果为空, 就将数据存入该位置; 如果不为空, 则继续查找下一个位置, 知道找到一个空的为止. 该技术是基于这样一个事实: 每个散列表都会有很多空的单元格, 可以使用他们来存储数据.

当存储数据使用的数组特别大时, 选择线性探测法要比开链法好. 这里有个公式, 常常可以帮助我们选择使用哪种碰撞解决办法: 如果数组的大小事带存储数据个数的1.5倍, 那么使用开链法; 如果数组的大小是待存储数据的两倍及两倍以上时, 那么使用线性探测法.

为了说明线性探测法的工作原理, 可以重写put()和get()方法. 为了实现一个真实的数据存取系统, 需要为HashTable类增加一个新的数组, 用来存储数据. 数组_table和_values并行工作, 当将一个键值保存到数组_table中同时将数据存入数组_values中相应的位置上.

在HashTable的构造函数中加入下面一行代码:

this._values = [];

在put()方法中使用线性探测技术:

...
put(key, data) {
    let pos = this._betterHash(key);
    
    if(this._table[pos] == undefined) {
        this._table[pos] = key;
        this._values[pos] = data;
    } else {
        while(this._table[pos] != undefined) {
            pos++
        };
        this._table[pos] = key;
        this._values[pos] = data;
    }
}
...

get()方法先搜索键在散列表中的位置, 如果找到, 则返回数组_values中对应位置上的数据; 如果没有找到, 则循环搜索, 知道找到对应的键或者数组中的单元为undefined时, 后者表示该键没有被存入散列表中.

...
get(key) {
    let hash = -1;
    hash = this._betterHash(key);

    if(hash > -1) {
        for(let i = hash; this._table[hash] != undefined; i++) {

            if(this._table[i] === key) {
                return this._values[i];
            };
        }
    };

    return undefined;
}
...