CoE KKU

กล่าวสำหรับ Open addressing ที่ใช้ quadratic probe แล้ว เมื่อตารางถูกใช้งานจนใกล้จะเต็ม running time ของการดำเนินการต่าง ๆ ก็จะมากขึ้นและการบรรจุค่าใหม่ก็อาจจะทำไม่ได้เลย สิ่งนี้ยังเกิดขึ้นกับกรณีที่มีการลบและบรรจุร่วมกันจำนวนมาก ๆ ด้วย ทางแก้หนึ่งก็คือ สร้างตารางขึ้นใหม่ให้มีขนาดเป็นสองเท่า (ร่วมกับการใช้ hash function ใหม่) แล้วย้ายข้อมูลในตารางเดิมไปลงในตารางใหม่ด้วยการคำนวณค่า hash value ใหม่สำหรับแต่ละค่าที่อ่านจากตารางแฮชเดิม (ที่เป็น non-deleted)

ตัวอย่างเช่น ทำการบรรจุค่าสมาชิก 13, 15, 24, และ 6 ลงในตารางแฮชแบบ open addressing hash table ที่มีขนาด 7 เซลล์ และใช้ฟังก์ชันแฮช $h(x) = x\ mod\ 7$ และใช้ linear probing ผลการทำงานแสดงในรูปที่ 5.19

ถ้าต้องการบรรจุ 23 ลงในตารางผลที่ได้ก็จะเป็นดังรูปที่ 5.20 และตารางจะมีจำนวนข้อมูลมากกว่า 70 % ของขนาดตาราง ดังนั้นจึงสร้างตารางใหม่ขึ้นโดยให้มีขนาดเป็น 17 เซลล์ เนื่องจากตัวเลข 17 นี้เป็นค่า prime ตัวแรกที่มีค่ามากกว่า 2 เท่าของของขนาดตารางเดิม ฟังก์ชันแฮชตัวใหม่ที่ใช้ คือ $h(x) = x\ mod\ 17$ แล้วทำการอ่านค่าในตารางเดิมตามลำดับ คือ 6, 15, 23, 24, และ 13 เพื่อคำนวณและบรรจุลงในตารางใหม่ที่สร้างขึ้น ผลที่ได้ก็จะเป็นดังรูปที่ 5.21

รูปที่ 5.21 Open addressing หลังจากการ rehash

วิธีการดำเนินการที่กล่าวมานี้เรียกว่า rehashing จะเห็นได้ว่าวิธีนี้เป็นวิธีที่มีค่าใช้จ่ายสูงมาก กล่าวคือมี running time เป็น $O(N)$, เนื่องจากมีสมาชิกอยู่ N ตัวที่ต้อง rehash และขนาดของตารางโดยประมาณคือ $2N$ ซึ่งดูจะเป็น running time ที่ไม่ค่อยจะดีนัก, อย่างไรก็ตามการจะต้องทำการ rehash ตารางก็ไม่ใช่เป็นสิ่งที่จะต้องเกิดขึ้นบ่อย ๆ โดยเฉพาะอย่างยิ่งมันจะต้องมีการบรรจุค่าใหม่เกิดขึ้นก่อนถึง $N/2$ ค่า ก่อนที่จะต้องทำการ rehash

การทำ Rehashing ที่ใช้ quadratic probe สามารถทำได้หลายทางด้วยกัน วิธีการหนึ่งคือให้ทำการ rehash ทันทีที่เซลล์ตารางถูกใช้ไปถึงครึ่งหนึ่งของขนาดเต็มจำนวน หรืออีกทางเลือกคือ ให้ทำการ rehash เมื่อการบรรจุค่าใหม่เกิดความล้มเหลวขึ้น ทางเลือกที่ 3 เป็นทางเลือกกลาง ๆ กล่าวคือ ให้ทำการ rehash เมื่อตารางมีค่า load factor ที่ระดับที่กำหนดไว้ และเนื่องจากประสิทธิภาพจะลดลงไปเรื่อย ๆ เมื่อ load factor มีค่าเพิ่มขึ้น ดังนั้นการเลือกใช้วิธีที่ 3 ด้วยการกำหนดค่า load factor ที่เหมาะสม ฟังก์ชัน rehash เป็นฟังก์ชันที่ง่ายในการ implement รูปที่ 5.22 แสดงฟังก์ชัน rehash

private void rehash()
{
	HashEntry [] oldArray = array;
	allocateArray( nextPrime( 2 * oldArray.length ) );
	currentSize = 0;
	for ( int i = 0; i < oldArray.length; i++)
		if ( oldArray[i] != null && oldArray[i].isActive )
			insert ( oldArray[i].element );
}

รูปที่ 5.22 ฟังก์ชัน rehash