CoE KKU

ถ้าค่า key เป็นเลขจำนวนเต็ม เพียงใช้ key mod TableSize ก็เป็นการเพียงพอ, เว้นเสียแต่บังเอิญว่าค่า key มีคุณสมบัติที่ไม่พึงประสงค์บางประการที่อาจจะต้องพิจารณาการเลือก hash function ด้วยความระมัดระวังมากขึ้น เช่น ถ้าค่า key ทั้งหมดเป็นค่าที่ลงท้ายด้วยศูนย์และขนาดของตารางคือ 10 การใช้ฟังก์ชันนี้ก็เป็นสิ่งที่ต้องหลีกเลี่ยง เพื่อหลีกเลี่ยงปัญหาดังกล่าวนี้ ปกติแล้วควรเลือกให้ขนาดตารางเป็น prime number ซึ่งถ้ากรณีที่ key เป็นเลขจำนวนเต็มแบบสุ่ม (random integers) นอกจากการใช้ฟังก์ชันนี้จะง่ายในการคำนวณแล้ว ยังสามารถกระจายค่า key ได้อย่างสม่ำเสมอด้วย

กรณีที่ค่า key เป็นสตริง (strings) การเลือก hash function จะต้องระมัดระวังมากเป็นพิเศษ ทางเลือกหนึ่งคือการใช้ผลบวกของค่า ASCII ของอักขระในสตริง ดังแสดงใน routine ในรูปที่ 5.2 ซึ่งไม่ซับซ้อนและทำงานได้รวดเร็ว อย่างไรก็ตาม ถ้าหากว่าตารางมีขนาดใหญ่ก็จะทำให้ฟังก์ชันไม่สามารถกระจาย key ได้ดี เช่น ถ้า TableSize = 10,007 (10,007 เป็น prime number) และถ้า key ทั้งหมดประกอบด้วยตัวอักษร 8 ตัวหรือน้อยกว่า เนื่องจากว่าค่า ASCII ปกติแล้วมีค่าสูงสุด 127, ดังนั้น hash function จะให้ค่าอยู่ระหว่าง 0 และ 1016, (ซึ่งคือ 127 * 8) นั่นคือฟังก์ชันแฮชที่ใช้นี้ก็จะไม่สามารถกระจายค่าออกในเซลล์ของตารางได้อย่างสม่ำเสมอ

public static int hash (String key, int tableSize)
{
	int hashVal = 0;
	for (int i = 0; i < key.length(); i++)
		hashVal += key.charAt(i);
	return hashVal % tableSize;
}

รูปที่ 5.2 hash function อย่างง่าย

public static int hash (String key, int tableSize)
{
	return (key.charAt(0) + 27 * key.charAt(1) + 
			729 * key.charAt(2) % tableSize;
}

รูปที่ 5.3 hash function

hash function ที่เป็นไปได้อีกรูปแบบหนึ่งแสดงดังรูปที่ 5.3 hash function นี้ใช้ข้อสมมุติว่า Key ประกอบด้วยอักษรอย่างน้อย 3 ตัว ตัวเลข 27 ในฟังก์ชันนี้คือจำนวนตัวอักษรในภาษาอังกฤษนับรวมช่องว่างด้วยหนึ่งตัวและตัวเลข 279 คือ 272 ฟังก์ชันนี้จะนำตัวอักษร 3 ตัวแรกมาใช้เท่านั้นและถ้าค่า key เป็นค่าสุ่มและตารางมีขนาดเป็น 10007 เช่นเดียวกับข้างบนที่กล่าวมาแล้วก็จะทำให้การกระจายค่าสม่ำเสมอ แต่โชคไม่ดีที่ภาษาอังกฤษที่ใช้ไม่เป็นแบบสุ่ม ถึงแม้ว่ามีหนทางเป็นไปได้ 263 = 17576 หนทางจากตัวอักษร 3 ตัวก็ตามแต่จากการตรวจสอบจากการใช้ในประทานนุกรมศัพท์พบว่าจำนวนที่แตกต่างของการใช้อักษรสามตัวมีเพียง 2851 คำเท่านั้น นั่นหมายความว่าจะมีเพียง 28 % ของขนาดตารางแฮชเท่านั้นที่ถูกใช้งาน ฟังก์ชันนี้ก็ไม่เหมาะที่ใช้ในกรณีที่ hash table มีขนาดใหญ่

รูปที่ 5.4 เป็น hash function อีกทางเลือกหนึ่ง ฟังก์ชันนี้ใช้อักษรทุกตัวใน key และคาดหวังได้ว่าจะกระจายค่าได้ดีโดยฟังก์ชันที่ใช้ คือ $∑_{i=0}^{KeySize-1} Key[KeySize-i-1]∙ 37^i$ โปรแกรมจะคำนวณค่า polynomial function (ของ 37) โดยใช้ Horner's rule เช่น คำนวณ $h_k = k_0 + 37k_1 + 37^2k_2$ ด้วยการใช้การใช้สูตรคำนวณ $h_k = ((k_2) * 37 + k_1) * 37 + k_0$ และ Horner's rule ขยายการคำนวณนี้ถึงดีกรีที่ $n$ ของ polynomial

public static int hash (String key, int tableSize)
{
	int hashVal = 0;
	for (int i = 0; i < key.length(); i++)
		hashVal = 37 * hashVal + key.charAt(i);
	hashVal %= tableSize;
	if (hashVal < 0)
		hashVal += tableSize;
	return hashVal;
}

รูปที่ 5.4 hash function ที่ดี

ฟังก์ชันในรูปที่ 5.4 ไม่ได้เป็นฟังก์ชันที่ดีที่สุดในแง่ของการกระจายค่าลงในตารางแต่เป็นฟังก์ชันที่ใช้การคำนวณที่ง่ายมาก ๆ และมีความรวดเร็วในการทำงาน อย่างไรก็ตามในทางปฏิบัติทั่วไปกรณีที่ค่า Key ประกอบด้วยอักษรจำนวนมาก ก็จะไม่ใช้อักษรทุกตัวมาคำนวณเพื่อลดเวลาในการคำนวณ

ปัจจัยที่มีผลต่อการจะเลือกใช้ตัวอักษรอย่างไรนั้นขึ้นอยู่กับความยาวและคุณสมบัติเฉพาะของสตริงที่เป็น keys เช่น ถ้า keys เป็นสตริงที่เป็นที่อยู่ (address) ที่ประกอบด้วยชื่อถนน เมือง รหัสพื้นที่ เราก็อาจจะเลือกตัวอักษร 2 – 3 ตัวจากชื่อถนนและ 2 – 3 ตัวจากชื่อเมืองและจากรหัสพื้นที่ ผู้เขียนโปรแกรมบางคนอาจจะเลือกใช้เฉพาะตัวอักษรที่อยู่ในตำแหน่งคี่ของสตริง

สิ่งสำคัญที่เหลือที่ยังไม่ได้กล่าวถึงในการเขียนโปรแกรม คือ การแก้ปัญหาการชน ที่เรียกว่า collision resolution ถ้าค่าแฮชที่ได้จากฟังก์ชันแฮชที่เกิดจากค่า key ตัวใหม่ที่จะบรรจุลงในตารางแฮชไปตรงกับเซลล์ที่มีค่าอื่นยึดครองอยู่แล้ว เรียกว่าเกิดการชน (collision) ซึ่งต้องการการแก้ไขเพื่อให้ค่าใหม่นั้นมีเซลล์ที่จะบรรจุลงได้ มีวิธีการหลายอย่างในการแก้ปัญหาการชน แต่ในที่นี้จะกล่าวถึงวิธีการพื้นฐาน 2 วิธี คือ: separate chaining (open hashing) และ open addressing (closed hashing)