Hash It Out: โครงสร้างข้อมูลที่รวดเร็วและมีประสิทธิภาพที่จะปฏิวัติโค้ดของคุณ!

ตารางแฮชเป็นโครงสร้างข้อมูลที่ใช้ในการจัดเก็บและเรียกข้อมูลอย่างรวดเร็ว ทำงานโดยใช้ฟังก์ชันแฮชเพื่อแมปคีย์ของรายการที่ถูกจัดเก็บไว้กับดัชนีเฉพาะในอาร์เรย์ ซึ่งทำให้สามารถเข้าถึงข้อมูลในเวลาคงที่ ไม่ว่าชุดข้อมูลจะมีขนาดเท่าใดก็ตาม .

ในตารางแฮช ข้อมูลจะถูกจัดเก็บไว้ใน คู่คีย์-ค่า เมื่อคุณต้องการเพิ่มหรือดึงข้อมูลรายการจากตาราง คุณจะต้องระบุคีย์และฟังก์ชันแฮชจะจับคู่คีย์กับดัชนีเฉพาะในอาร์เรย์ จากนั้นค่าจะถูกจัดเก็บไว้ที่ดัชนีนั้น หรือดึงข้อมูลจากดัชนีนั้น แล้วแต่กรณี

ตารางแฮชมีประสิทธิภาพมากในการจัดเก็บและเรียกข้อมูล และมีการใช้กันอย่างแพร่หลายในแอปพลิเคชันต่างๆ เช่น ฐานข้อมูล แคช และแฮชแมปในภาษาการเขียนโปรแกรม นำเสนอการค้นหา การแทรก และการลบที่รวดเร็ว ทำให้เป็นตัวเลือกยอดนิยมสำหรับการใช้งานอาร์เรย์ ชุด และแผนที่ที่เชื่อมโยง

การใช้งานนี้มีขนาดคงที่สำหรับตารางแฮช ซึ่งระบุไว้เมื่อสร้างอ็อบเจ็กต์ HashTable มีเมธอด hash() ที่ใช้คีย์เป็นอินพุตและส่งกลับดัชนีในอาร์เรย์ที่ควรจัดเก็บหรือดึงค่า วิธีการ insert(), get() และ remove() ใช้วิธีการ hash() เพื่อค้นหาดัชนี จากนั้นดำเนินการที่เกี่ยวข้องกับค่าที่เก็บไว้ที่ดัชนีนั้น

class HashTable {
  constructor(size) {
    this.size = size;
    this.buckets = new Array(size);
  }

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

  insert(key, value) {
    let index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    this.buckets[index].push({key, value});
  }

  get(key) {
    let index = this.hash(key);
    if (!this.buckets[index]) return null;
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i].key === key) {
        return this.buckets[index][i].value;
      }
    }
    return null;
  }

  remove(key) {
    let index = this.hash(key);
    if (!this.buckets[index]) return null;
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i].key === key) {
        this.buckets[index].splice(i, 1);
        return;
      }
    }
  }
}

const hashTable = new HashTable(10);

hashTable.insert('abc', 123);
hashTable.insert('def', 456);

console.log(hashTable.get('abc')); // 123
console.log(hashTable.get('def')); // 456

hashTable.remove('abc');
console.log(hashTable.get('abc')); // null

ฟังก์ชันแฮช

ฟังก์ชันแฮชคือฟังก์ชันที่รับอินพุต (เรียกว่า “คีย์”) และส่งกลับเอาต์พุตที่มีขนาดคงที่ (เรียกว่า “ค่าแฮช” หรือ “โค้ดแฮช”) ที่คำนวณตามคีย์ วัตถุประสงค์หลักของฟังก์ชันแฮชคือการนำอินพุตขนาดใหญ่และแมปเข้ากับเอาต์พุตที่เล็กกว่าในลักษณะที่ทำให้ง่ายต่อการค้นหาคีย์ต้นฉบับตามค่าแฮช แต่เป็นไปไม่ได้ที่จะสร้างคีย์ต้นฉบับตาม กับค่าแฮชเพียงอย่างเดียว

คุณสมบัติหลักของฟังก์ชันแฮชที่ดีคือ:

• มีประสิทธิภาพในการคำนวณ: ฟังก์ชันแฮชควรรวดเร็วในการคำนวณและไม่ต้องใช้ทรัพยากรจำนวนมาก
• การกำหนด: อินพุตเดียวกันควรสร้างเอาต์พุตเดียวกันเสมอ เพื่อให้สามารถค้นหาคีย์เดียวกันได้อย่างง่ายดายโดยใช้ค่าแฮชเดียวกัน
• การกระจายแบบสม่ำเสมอ: เอาต์พุตของฟังก์ชันแฮชควรมีการกระจายเท่าๆ กันในช่วงของค่าแฮชที่เป็นไปได้ เพื่อให้คีย์มีการกระจายเท่าๆ กันทั่วทั้งตารางแฮช
• ทนต่อการชนกัน: ฟังก์ชันแฮชควรลดความน่าจะเป็นที่คีย์สองคีย์ที่แตกต่างกันที่มีค่าแฮชเท่ากัน หรือที่เรียกว่าการชนกัน

ฟังก์ชันแฮชมีการใช้กันอย่างแพร่หลายในแอปพลิเคชันต่างๆ เช่น การจัดเก็บและการเรียกค้นข้อมูล การเข้ารหัส และการขุดข้อมูล ในบริบทของตารางแฮช ฟังก์ชันแฮชที่ดีควรจะสามารถแมปคีย์ของรายการที่ถูกจัดเก็บไว้กับดัชนีที่ไม่ซ้ำกันในอาร์เรย์ตารางแฮช เพื่อให้แต่ละคีย์สามารถแทรกและดึงข้อมูลได้อย่างง่ายดาย

มีฟังก์ชันแฮชที่แตกต่างกันมากมายที่สามารถใช้ได้ และตัวเลือกของฟังก์ชันแฮชนั้นขึ้นอยู่กับข้อกำหนดเฉพาะของแอปพลิเคชัน ฟังก์ชันแฮชทั่วไปบางฟังก์ชัน ได้แก่ แฮชแบบโมดูโล แฮชสากล และแฮชที่เข้ารหัส

ต่อไปนี้คือตัวอย่างอื่นๆ ของฟังก์ชันแฮชที่สามารถใช้ในตารางแฮช:

โมดูโล่แฮช

ฟังก์ชันแฮชนี้ใช้ตัวดำเนินการแบบโมดูโลเพื่อจับคู่คีย์กับดัชนีในอาร์เรย์ตารางแฮช ตัวอย่างเช่น:

function moduloHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % size;
}

แฮชการเข้ารหัส

นี่คือฟังก์ชันแฮชประเภทหนึ่งที่ใช้ฟังก์ชันแฮชที่สร้างแบบสุ่มสำหรับแต่ละคีย์ ซึ่งทำให้ทนทานต่อการโจมตีจากการชนกันมากขึ้น นี่คือตัวอย่างของฟังก์ชันแฮชสากล:

const crypto = require('crypto');

function cryptographicHash(key) {
  return crypto.createHash('sha1').update(key).digest('hex');
}

ตารางแฮชขนาดไดนามิก

ตารางแฮชสามารถนำไปใช้กับอาเรย์ปรับขนาดแบบไดนามิกได้ ซึ่งหมายความว่าขนาดของอาเรย์สามารถเปลี่ยนแปลงได้ตามจำนวนองค์ประกอบในตาราง

วิธีทั่วไปวิธีหนึ่งในการนำตารางแฮชขนาดไดนามิกไปใช้คือการใช้ปัจจัยโหลด ซึ่งเป็นการวัดว่าตารางแฮชเต็มแค่ไหน เมื่อจำนวนองค์ประกอบในตารางแฮชเกินเกณฑ์ที่กำหนด (กำหนดโดยปัจจัยโหลด) อาร์เรย์จะถูกปรับขนาดให้ใหญ่ขึ้นเพื่อให้มีที่ว่างสำหรับองค์ประกอบเพิ่มเติม ในทำนองเดียวกัน เมื่อจำนวนองค์ประกอบต่ำกว่าเกณฑ์ที่กำหนด อาเรย์จะถูกปรับขนาดให้เล็กลงเพื่อประหยัดพื้นที่

นี่คือตัวอย่างวิธีการใช้ตารางแฮชขนาดไดนามิกใน JavaScript โดยใช้ไวยากรณ์ ES6:

class HashTable {
  constructor() {
    this.size = 8;
    this.buckets = new Array(this.size);
    this.numElements = 0;
  }

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

  insert(key, value) {
    this.numElements++;
    let index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    this.buckets[index].push({ key, value });
    if (this.numElements > this.size * 0.75) {
      this.resize(this.size * 2);
    }
  }

  get(key) {
    let index = this.hash(key);
    if (!this.buckets[index]) return null;
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i].key === key) {
        return this.buckets[index][i].value;
      }
    }
    return null;
  }

  remove(key) {
    this.numElements--;
    let index = this.hash(key);
    if (!this.buckets[index]) return null;
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i].key === key) {
        this.buckets[index].splice(i, 1);
        if (this.numElements < this.size * 0.25) {
          this.resize(this.size / 2);
        }
        return;
      }
    }
  }

  resize(newSize) {
    let oldBuckets = this.buckets;
    this.size = newSize;
    this.buckets = new Array(this.size);
    this.numElements = 0;
    for (let i = 0; i < oldBuckets.length; i++) {
      if (oldBuckets[i]) {
        for (let j = 0; j < oldBuckets[i].length; j++) {
          this.insert(oldBuckets[i][j].key, oldBuckets[i][j].value);
        }
      }
    }
  }
}

การใช้งานในตัวตารางแฮช

JavaScript มีคลาสในตัวหลายคลาสที่ใช้ตารางแฮชเพื่อจัดเก็บและดึงข้อมูลอย่างมีประสิทธิภาพ ตัวอย่างบางส่วนได้แก่:

• แผนที่ - คลาส Map คือชุดของคู่คีย์-ค่าที่สามารถวนซ้ำตามลำดับที่เพิ่ม ใช้ตารางแฮชเพื่อจัดเก็บข้อมูลและให้การแทรก การลบ และเวลาในการค้นหา O(1) ที่มีประสิทธิภาพ
• ชุด - คลาส Set คือชุดของค่าที่ไม่ซ้ำกันซึ่งสามารถวนซ้ำตามลำดับที่เพิ่มเข้าไป นอกจากนี้ยังใช้ตารางแฮชเพื่อจัดเก็บข้อมูลและให้การแทรก การลบ และเวลาในการค้นหา O(1) ที่มีประสิทธิภาพ

คลาสในตัวเหล่านี้มอบวิธีที่สะดวกในการใช้ตารางแฮชใน JavaScript และมีประโยชน์มากสำหรับการจัดเก็บและจัดการข้อมูลอย่างมีประสิทธิภาพ

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