CoE KKU

การแก้ปัญหาการชนด้วยวิธี separate chaining (open hashing) ใช้ลิสต์ (list) เพื่อเก็บรายการของค่าที่ hash แล้วได้ค่าเท่ากัน โดยเราจะใช้ลิสต์แบบที่มี header เพื่อความสะดวกในการใช้งาน เพื่อความสะดวกในการอธิบาย ในที่นี้เราจะสมมุติให้ค่า key มีค่าเป็นเลข perfect squares จำนวน10 ตัว และใช้ hashing function อย่างง่ายคือ $hash(x) = x mod 10$ (ในกรณีนี้ค่าของขนาดของตารางไม่ได้เป็นค่า prime เพื่อเป็นตัวอย่างเท่านั้น) รูปที่ 5.5 แสดงผลการ hash

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

    public class SeparateChainingHashTable 
    {   public SeparateChainingHashTable( )  { /* Figure 5.8 */ }
        public SeparateChainingHashTable( int size ) { /* Figure 5.8 */ }
        public void insert( Hashable x )  { /* Figure 5.10 */}
        public void remove( Hashable x )  {/* Figure 5.9 */}
        public Hashable find( Hashable x )  {/* Figure 5.9 */}
        public void makeEmpty( ) {/* Figure 5.8 */}
        public static int hash( String key, int tableSize )  {/* Figure 5.4 */}
        private static final int DEFAULT_TABLE_SIZE = 101;
        private LinkedList [ ] theLists;            /** The array of Lists. */
        private static int nextPrime( int n )
        {  if( n % 2 == 0 )  n++;
            for( ; !isPrime( n ); n += 2 )    ;
            return n;
        }
        private static boolean isPrime( int n )
        {  if ( n == 2 || n == 3 )  return true;
            if ( n == 1 || n % 2 == 0 )  return false;
            for ( int i = 3; i * i <= n; i += 2 )
                if ( n % i == 0 )
                    return false;
            return true;
        }
}

รูปที่ 5.6 โครงร่างของคลาสสำหรับตารางแฮชที่ใช้ separate chaining

โครงร่างของคลาสที่ใช้สำหรับ open hashing แสดงไว้ในรูปที่ 5.6 โครงสร้างของตารางแฮชประกอบด้วยอะเรย์ของลิงค์ลิสต์ซึ่งกำหนดขึ้นใน constructor

hash tables ที่ใช้ในบทนี้ทำงานได้เฉพาะสำหรับ objects ที่ใช้ implement จาก Hashable interface เท่านั้น และ Hashable interface ประกอบด้วย method เดียว ดังรูปที่ 5.7 คลาส Employee (รูปที่ 5.7) ใช้ implement จาก Hashable interface โดยการใช้ hash function ในรูปที่ 5.4 ซึ่งเป็นฟังก์ชันในคลาส SeparateChainingHashTable รูปที่ 5.8 แสดง constructor และฟังก์ชัน makeEmpty

public interface Hashable 
{ int hash( int tableSize );  }
public class Employee implements Hashable 	// Example of the Employee class
{	public int hash( int tableSize )
	{ return SeparateChainingHashTable( name, tableSize ); }
	public boolean equals ( Object rhs )
	{ return name.equals (  ((Employee)rhs).name); }
	private String name;
	private double salary;
	private int seniority;
		// Additional fields and methods
}

รูปที่ 5.7 Hashable interface

public SeparateChainingHashTable( ) 
{      this( DEFAULT_TABLE_SIZE );   }
public SeparateChainingHashTable( int size )
{      theLists = new LinkedList[ nextPrime( size ) ];
       for( int i = 0; i < theLists.length; i++ )
                theLists[ i ] = new LinkedList( );
}
 public void makeEmpty( )
 {     for( int i = 0; i < theLists.length; i++ )
                theLists[ i ].makeEmpty( );
 }

รูปที่ 5.8 Constructors และฟังก์ชัน makeEmpty ของตารางแฮชที่ใช้ separate chaining

ฟังก์ชัน find(x) ให้ค่ากลับเป็น reference ที่อ้างอิงออปเจ็กต์ที่ตรงกับ x โปรแกรมสำหรับฟังก์ชัน find และ remove แสดงในรูปที่ 5.9

public void remove( Hashable x )
{     theLists[ x.hash( theLists.length ) ].remove( x );
}
 
public Hashable find( Hashable x )
{     return (Hashable)theLists[ x.hash( theLists.length ) ].find( x ).retrieve( );
} 

รูปที่ 5.9 ฟังก์ชัน find และ remove

public void insert( Hashable x )
 {   LinkedList whichList = theLists[ x.hash( theLists.length ) ];
     LinkedListItr itr = whichList.find( x );
     if  ( itr.isPastEnd( ) )
          whichList.insert( x, whichList.zeroth( ) );
} 

รูปที่ 5.10 ฟังก์ชัน insert

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

เราสามารถใช้โครงสร้างแบบอื่น ๆ แทนที่จะเป็นลิงค์ลิสต์ เช่นใช้ binary search tree หรือแม้กระทั่งใช้ตารางแฮชอีกตารางหนึ่งก็ได้

เรากำหนดนิยามของ load factor ($\lambda$) ของตารางแฮชว่าเป็นอัตราส่วนระหว่างจำนวนของสมาชิกที่มีอยู่ในตารางแฮชต่อขนาดของตาราง เช่นในตัวอย่างรูปตารางแฮชข้างบนจะมีค่า $\lambda = 1.0$ ความยาวเฉลี่ยของลิสต์ คือค่า $\lambda$ นั่นเอง

การทำงานการค้นหาค่าจะต้องใช้เวลาที่เป็นค่าคงที่ในการคำนวณ hash function เพื่อระบุตำแหน่งเซลล์บวกกับเวลาที่จะต้องใช้ไปในการท่องไปในลิสต์เพื่อตรวจสอบค่า กรณีการค้นหาที่ไม่ประสบความสำเร็จ (unsuccessful search) จำนวนโนดที่ต้องท่องไปในลิสต์โดยเฉลี่ยคือ $\lambda$ (เพราะต้องท่องไปในลิสต์จนจบลิสต์) กรณีการค้นหาที่ประสบความสำเร็จ (successful search) คือพบค่าที่ต้องค้นหาก็จะต้องใช้การท่องไปในลิสต์โดยเฉลี่ยประมาณ $\lambda + (\lambda/2)$ โนด, เนื่องจากอย่างน้อยต้องท่องไปหนึ่งโนดเสมอที่หัวของลิสต์ และคาดหวังว่าอาจจะต้องท่องไปเป็นระยะทางครึ่งหนึ่งของลิสต์ เหตุที่เราสามารถกล่าวเช่นนี้ได้ก็เนื่องจากว่าลิสต์ที่เรากำลังทำการค้นหาค่าอยู่นั้นจะมีโนดอยู่หนึ่งโนดที่มีค่าที่เราต้องการและมีหรือไม่มีโนดอื่น ๆ อยู่อีกก็เป็นได้

ค่าคาดหวังที่เป็นได้ของจำนวนโนดอื่น ๆ ที่ว่านี้ที่มีอยู่ในตารางที่มีขนาดสมาชิก N ตัวและมีจำนวนลิสต์อยู่ M ลิสต์ ก็คือค่า $(N – 1) M = \lambda - 1/M$ ซึ่งก็คือประมาณ $\lambda$ นั่นเอง เพราะปกติ M มีขนาดใหญ่มาก โดยเฉลี่ยแล้วเราจะต้องท่องไปใน “โนดอื่น ๆ ที่ว่านี้” เป็นระยะครึ่งหนึ่งของความยาวของมัน (คือ $\lambda/2$) บวกกับอีกหนึ่งโนดที่มีค่าเท่ากับที่ต้องการ ดังนั้นจึงได้ค่าเฉลี่ยประมาณ $1 + (\lambda/2)$ โนด

จากการวิเคราะห์แสดงให้เห็นว่าขนาดของตารางอย่างเดียวไม่มีความสำคัญแต่ปัจจัยที่มีผลต่อการทำงานคือค่า load factor กฎทั่วไปในการใช้ open hashing คือการเลือกใช้ตารางที่มีขนาดเท่ากับจำนวนสมาชิกที่คาดว่าจะมี (หรือก็คือ $\lambda \approx 1$) และดังที่กล่าวมาก่อนหน้านี้แล้วว่าค่าของขนาดของตารางเป็นค่า prime number เพื่อให้การกระจายค่าในตารางเป็นไปอย่างสม่ำเสมอได้