散列表

  1. 散列表也叫哈希表，是根据关键码值（key, value）而直接进行访问的数据结构，它是通过键码值映射到表中一个位置来访问记录的，散列表后的数据可以快速的插入和使用，散列使用的数据结构叫做散列表；

  2. 示例代码

    // 初始化散列表
let dic = new Map();

// 添加 key -> value 键值对
dic.set("小力", 10001);
dic.set("小特", 10002);
dic.set("小扣", 10003);

// 从姓名查找学号
dic.get("小力"); // -> 10001
dic.get("小特"); // -> 10002
dic.get("小扣"); // -> 10003

Hash 函数设计示例

  1. 将三人的姓名存储至以下数组中，则各姓名在数组中的索引分别为 0, 1, 2

    let names = { 0: "小力", 1: "小特", 2: "小扣" };

  2. 构造一个简单的 Hash 函数 hash(key) = (key−1) % 10000

    function hash(id) {
    let index = (id - 1) % 10000;
    return index;
}

  3. 构建了以学号为 key 、姓名对应的数组索引为 value 的散列表；利用此 Hash 函数，则可在 O(1) 时间复杂度下通过学号查找到对应姓名；

    names[hash(10001)] // 小力
names[hash(10002)] // 小特
names[hash(10003)] // 小扣

  4. 以上设计只适用于此示例，实际的 Hash 函数需保证低碰撞率、 健壮性等，以适用于各类数据和场景；

参考资料

  1. 卡尔：《代码随想录》

打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 散列表
  2. 2. Hash 函数设计示例
  3. 3. 参考资料