โครงสร้างข้อมูลและอัลกอริทึม - ตารางแฮช

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

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

แฮช

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

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)
ซีเนียร์ สำคัญ กัญชา ดัชนีอาร์เรย์
1 1 1% 20 = 1 1
2 2 2% 20 = 2 2
3 42 42% 20 = 2 2
4 4 4% 20 = 4 4
5 12 12% 20 = 12 12
6 14 14% 20 = 14 14
7 17 17% 20 = 17 17
8 13 13% 20 = 13 13
9 37 37% 20 = 17 17

Linear Probing

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

ซีเนียร์ สำคัญ กัญชา ดัชนีอาร์เรย์ หลังจาก Linear Probing ดัชนีอาร์เรย์
1 1 1% 20 = 1 1 1
2 2 2% 20 = 2 2 2
3 42 42% 20 = 2 2 3
4 4 4% 20 = 4 4 4
5 12 12% 20 = 12 12 12
6 14 14% 20 = 14 14 14
7 17 17% 20 = 17 17 17
8 13 13% 20 = 13 13 13
9 37 37% 20 = 17 17 18

การทำงานขั้นพื้นฐาน

ต่อไปนี้เป็นการดำเนินการหลักพื้นฐานของตารางแฮช

  • Search - ค้นหาองค์ประกอบในตารางแฮช

  • Insert - แทรกองค์ประกอบในตารางแฮช

  • delete - ลบองค์ประกอบจากตารางแฮช

DataItem

กำหนดรายการข้อมูลที่มีข้อมูลและคีย์ตามที่จะดำเนินการค้นหาในตารางแฮช

struct DataItem {
   int data;
   int key;
};

วิธีแฮช

กำหนดวิธีการแฮชเพื่อคำนวณรหัสแฮชของคีย์ของรายการข้อมูล

int hashCode(int key){
   return key % SIZE;
}

การดำเนินการค้นหา

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

ตัวอย่าง

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

แทรกการทำงาน

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

ตัวอย่าง

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

ลบการทำงาน

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

ตัวอย่าง

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินกัญชาในโปรแกรมภาษา C โปรดคลิกที่นี่