การเพิ่มข้อมูลใน Hash Table ด้วย JavaScript

เมื่อเพิ่มข้อมูลใน Hash Table สิ่งสำคัญที่สุดคือการจัดการการชน (collision resolution) เราจะใช้วิธี chaining สำหรับการแก้ปัญหานี้ มีอัลกอริธมอื่นๆ ที่คุณสามารถอ่านเพิ่มเติมได้ที่: https://en.wikipedia.org/wiki/Hash_table#Collision_resolution

มาดูการนำไปใช้งานกัน เราจะสร้าง hash function ที่ทำงานกับจำนวนเต็มเพื่อความเรียบง่าย แต่อัลกอริธมที่ซับซ้อนกว่าสามารถนำไปใช้กับทุกประเภทของออบเจกต์ได้:

ตัวอย่างโค้ด

put(key, value) {
  let hashCode = hash(key);
  for(let i = 0; i < this.container[hashCode].length; i++) {
    // แทนที่ค่าที่มีอยู่กับคีย์ที่กำหนดถ้ามีอยู่แล้ว
    if(this.container[hashCode][i].key === key) {
      this.container[hashCode][i].value = value;
      return;
    }
  }
  // เพิ่มคู่ข้อมูลที่ปลาย array
  this.container[hashCode].push(new this.KVPair(key, value));
}

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

let ht = new HashTable();
ht.put(10, 94);
ht.put(20, 72);
ht.put(30, 1);
ht.put(21, 6);
ht.put(15, 21);
ht.put(32, 34);
ht.display();

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

0:
1:
2:
3:
4: { 15: 21 }
5:
6:
7:
8: { 30: 1 }
9: { 20: 72 }
10: { 10: 94 } -->{ 21: 6 } -->{ 32: 34 }