登录
当前位置： 首页 > 知识库问答 >
问题：

使用javascript实现哈希表

萧永长
2023-03-14

我正在尝试使用javascript实现哈希表。目前，一切都正常，但我的get方法在给定特定键的哈希表中检索值时遇到了麻烦。我使用线性探测来避免冲突。当我散列键“亚历杭德罗”时，我将键映射到0索引。然后我将其添加到我的哈希表中。然后我尝试“Rosalby”，它也映射到0索引。我使用线性探测来找到下一个可用的插槽，在我的例子中，空索引是1，我将Rosalby的值放在那个插槽中。到目前为止，我似乎很好地处理了我的冲突。然而，当我试图在get方法中获取值时，我无法获得正确的值，这就是我的哈希表的样子。

另外，我想提到的是，我已经将哈希表的大小扩大了，并且在给定特定键的情况下得到了正确的值，这仅仅是因为我没有冲突。提前谢谢你。

js prettyprint-override">// Hash table implementation
class HashTable {
  // constructor functio
  constructor(size) {
    this.size = size;
    this.buckets = this.initArray(size);
    this.limit = 0;
  }

  // init array function
  initArray(size) {
    // init an array
    const array = [];

    // populate the array base on the size
    for (let i = 0; i < size; i++) {
      // push null to the array
      array.push(null);
    }
    // return the array
    return array;
  }

  // mapping key to index
  hash(key) {
    let total = 0;

    // get unique code of character in the string
    for (let i = 0; i < key.length; i++) {
      let keyCode = key.charCodeAt(i)
      //  console.log("Key code:", keyCode)

      // sum up the unique code
      total += keyCode;
      // console.log(total); 
    }
    // mod the total to the size of the hash table
    const hashIndex = total % this.size;
    // return that index
    return hashIndex;
  }

  // put method
  put(key, value) {
    // throw an erro if hashTable is full
    if (this.limit >= this.size) throw "Hash Table is full";

    // hash the key
    let hashIndex = this.hash(key);
    // console.log(hashIndex);

    // linear probing
    while (this.buckets[hashIndex] != null) {
      hashIndex++;

      hashIndex = hashIndex % this.size;
    }

    // add the value at that key to the buckets array
    this.buckets[hashIndex] = value;

    // increase the limit
    this.limit++;
  }

  // get method
  get(key) {
    // hash the key
    let hashIndex = this.hash(key);
    let value = this.buckets[hashIndex];

    // return the value at that index
    return value;
  }
} // end of hash table

// sanity check
const ht = new HashTable(3);
console.log(ht);
// ht.hash("Rosalby");
console.log();
ht.put("Alejandro", "555-5555");
ht.put("Rosalby", "123-1231");
ht.put("Lalaland", "000-0000");
// ht.put("Lalaland", "919-1919");
console.log();
console.log(ht);
console.log("Alejandro:", ht.get("Alejandro"), "Rosalby:", ht.get("Rosalby"), "Lalaland:", ht.get("Lalaland"));

哈希表控制台日志

共有2个答案

拓拔野
2023-03-14 
class HashTable {
  constructor(size){
    this.data = new Array(size);
    // this.data = [];
  }

  _hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }

  get(key){
    const address = this._hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }
  
  keys(){
    const keysArray = [];
    console.log(this.data.length);
    for (let i = 0; i < this.data.length; i++){
      if(this.data[i]){
        keysArray.push(this.data[i][0][0])
      }
    }
    return keysArray;
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')
myHashTable.keys()
丰胤运
2023-03-14

下面是哈希表的一个快速实现：

class HashTable
{
    constructor(getHash)
    {
        if(!getHash) throw "Argument is null: getHash";
        
        this.getHash = getHash;
        this.buckets = {};
        this._count = 0;
    }
    
    //  throws an exception if the key already exists
    add(key, value)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket)
        {
            this.buckets[hashCode] = [{key, value}];
            ++this._count;
            return;
        }
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) throw "Duplicate key.";
        }
        bucket.push({key, value});
        ++this._count;
    }
    
    //  replaces the value if the key already exists
    set(key, value)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket)
        {
            this.buckets[hashCode] = [{key, value}];
            ++this._count;
            return;
        }
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) 
            {
                item.value = value;
                return;
            }
        }
        bucket.push({key, value});
        ++this._count;
    }

    get(key, defaultValue)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket) return defaultValue;
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) return item.value;
        }
        return defaultValue;
    }

    has(key)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket) return false;
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) return true;
        }
        return false;
    }
    
    get count()
    {
        return this._count;
    }
}

HashTable.unitTests = function()
{
    function getHash(value)
    {
        const stringValue = String(value);
        let result = 0;
        for(let length = stringValue.length, i = 0; i < length; ++i) result ^= stringValue.charCodeAt(i);
        return result;
    }
    
    let ht;
    
    //  empty
    ht = new HashTable(getHash);
    if (ht.count != 0) throw "failed";
    if (ht.has(null)) throw "failed";
    if (ht.has("")) throw "failed";
    if (ht.get(null) != void (0)) throw "failed";
    if (ht.get("") != void (0)) throw "failed";
    if (ht.get(null, 1) != 1) throw "failed";

    //  add new
    ht = new HashTable(getHash);
    ht.add("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  set new
    ht = new HashTable(getHash);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  add duplicate
    ht = new HashTable(getHash);
    ht.add("a", 1);
    try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }

    //  add+set duplicate
    ht = new HashTable(getHash);
    ht.add("a", 1);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  set+add duplicate
    ht = new HashTable(getHash);
    ht.set("a", 1);
    try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }

    //  set duplicate
    ht = new HashTable(getHash);
    ht.set("a", 1);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  add multiple
    ht = new HashTable(getHash);
    ht.add("a", 1);
    ht.add("b", 2);
    if (ht.count != 2) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (!ht.has("b")) throw "failed";
    if (ht.get("a") != 1) throw "failed";
    if (ht.get("b") != 2) throw "failed";

    //  add with collision
    ht = new HashTable(getHash);
    ht.add("ab", 1);    //  hash code 3
    ht.add("ba", 2);    //  hash code 3
    if (ht.count != 2) throw "failed";
    if (!ht.has("ab")) throw "failed";
    if (!ht.has("ba")) throw "failed";
    if (ht.get("ab") != 1) throw "failed";
    if (ht.get("ba") != 2) throw "failed";

    //  set with collision
    ht = new HashTable(getHash);
    ht.set("ab", 1);    //  hash code 3
    ht.set("ba", 2);    //  hash code 3
    if (ht.count != 2) throw "failed";
    if (!ht.has("ab")) throw "failed";
    if (!ht.has("ba")) throw "failed";
    if (ht.get("ab") != 1) throw "failed";
    if (ht.get("ba") != 2) throw "failed";
}

HashTable.unitTests();
console.log("OK");
<html>
<head>
<script src="HashTable.js"></script>
</head>
<body>
</body>
</html>
 类似资料：
  • JavaScript哈希图如何实现？

    问题内容： 我目前在OpenLayers上工作，并且有大量的数据可以绘制到矢量层中（大于100000个矢量）。 我现在正尝试将所有这些向量放入JavaScript哈希图中以分析性能。我想知道如何在JavaScript中实现哈希图，它是真正的哈希函数还是只是使用简单数据结构和搜索算法的包装函数？ 问题答案： 每个javascript对象都是一个简单的hashmap，它仅接受字符串值作为其键，因此您可

  • 图实现：为什么不使用哈希？

    也许我没有看到什么或者我忘记了在计算运行时考虑的事情，所以请告诉我。

  • 本地敏感哈希实现？

    问题内容： 在C / C ++ / Java / C＃中是否有相对简单易懂（易于实现）的局部敏感哈希示例？ 我想了解更多有关此概念的信息，因此想在几个文本文件上尝试实现只是为了了解其工作原理，因此我不需要任何高性能或任何内容……仅是哈希示例对于相似的输入返回相似的哈希值的函数。我可以通过后面的例子从中学到更多。:) 问题答案： 对于字符串，您可以使用近似匹配算法。 产生随机字串 对于所有字符串，使

  • Python Frozenset哈希算法/实现

    问题内容： 我目前正在尝试了解为Python的内置数据类型定义的哈希函数背后的机制。该实现显示在底部，以供参考。我特别感兴趣的是选择此分散操作的原理： 每个元素的哈希值在哪里。有人知道这些来自哪里吗？（也就是说，是否有任何特定的原因来选择这些数字？）还是只是简单地任意选择了它们？ 这是来自官方CPython实现的代码片段， 以及Python中的等效实现： 问题答案： 除非Raymond Hetti

  • 在Linux内核哈希列表实现中使用双指针

    问题内容： 我试图了解链表和哈希表的Linux内核实现。实现的链接在这里。我了解链表的实现。但是我对为什么在hlist（* pprev）中使用双指针感到困惑。hlist的链接在这里。我知道hlist用于实现哈希表，因为列表的头仅需要一个指针，并且可以节省空间。为什么不能使用单个指针（就像链接列表一样 prev）来完成？请帮我。 问题答案： 原因可以在以下注释之一中找到： 如果您使用的是 prev而

  • 在javascript中构建哈希表和完善的哈希函数

    我正在使用Google Maps API，觉得除了大量的语句之外，还有一种更好的方法来搜索全景图像。我认为使用外部哈希表会更有效，更容易维护。每个图像都有一个唯一的，我可以定义它。阅读哈希表，我相信我的说法是正确的，我可以做一个表和完善的函数，以获得我需要的数据，在恒定的时间。有没有一个很好的资源如何构建这个？我对哈希一点经验都没有。 我的逻辑是这样的：每个图像都以的形式保存在一个目录中，其中是一

相关问答

在javascript中隐藏哈希数哈希初始化的Ruby哈希使用线性探测插入哈希表在C中实现哈希表（使用链表避免冲突）的必要结构？实现链表并存储文本文件的哈希表

相关文章

Android中SHA1哈希实现的问题哈希表或哈希表中的重新哈希处理Powershell使用嵌套哈希表实例 嵌套哈希表的2种写法例子PHP哈希表实现算法原理解析使用JavaScript解析URL哈希/片段标识符

相关阅读

DBMS动态哈希DBMS静态哈希Swif哈希集合什么是哈希？树哈希常用的方式

相关工具

希科系统(CxServer)《Redis 设计与实现》《Apache Spark 设计与实现》UIWebView中调用Javascriptmd5和sha加密代码实现

相关文档

现代 JavaScript 教程常用算法实现方法Redis 设计与实现如何实现自己的 jQuery使用 Spring Cloud 与 Docker 实战微服务
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.