Algorithms/load factor and rehashing

تتطلب إضافة زوج مفتاح (K) - قيمة (V) إلى جدول التقطيع الخطوات التالية:

1. يحوّل المفتاح إلى عدد صحيح ذي قيمة أصغر (يسمّى شيفرة التقطيع) باستخدام دالة التقطيع.
2. تستخدم شيفرة التقطيع لإيجاد موقع (hashCode % arrSize) ويجري البحث في القائمة المترابطة في ذلك الموقع (السلاسل المنفصلة Separate chaining) بحثًا عن المفتاح.
3. إن عُثر على ذلك المفتاح فإنّ الدالة تحدّث قيمته، وإن لم يعثر عليه يُخزّن زوج K-V كعقدة جديدة في القائمة المترابطة.

التعقيد ومعامل التحميل

• يعتمد الوقت المستغرق لتنفيذ الخطوة الأولى على المفتاح وعلى دالة التقطيع. فعلى سبيل المثال إن كان المفتاح عبارة عن سلسلة نصية "abcd" فيمكن لدالة التقطيع أن تعتمد على طول السلسلة النصية، ولكن عند استخدام أعداد كبيرة من العناصر التي ستدخل إلى الجدول، فإنّ طول المفاتيح سيكون ضئيلًا جدًّا مقارنة بعدد العناصر؛ لذا يمكن القول أنّ العملية ستجري في زمن ثابت وسيبلغ التعقيد الزمني لها O(1)‎.
• تتطلب الخطوة الثانية التنقل عبر قائمة أزواج K-V الموجودة في الموقع المحدد. أسوأ الاحتمالات هو أن جميع العناصر موجودة في الموقع ذاته وبيلغ التعقيد الزمني لهذه الخطوة عندها O(n)‎. ولكن أجريت الكثير من الأبحاث لجعل دوال التقطيع توزّع المفاتيح في المصفوفة بصورة نظامية؛ لذا هذا الاحتمال غير وارد إطلاقًا.
• لو كان هناك n من العناصر وكان حجم المصفوفة هو b فإن معدّل العناصر في كل موقع سيكون n/b، وتسمّى هذه القيمة بمعامل الحمولة load factor والذي يمثّل حمولة جدول التقطيع.
• يجب الإبقاء على قيمة منخفضة لمعامل الحمولة، وبذلك يصبح عدد العناصر في الموقع الواحد أقلّ ما يمكن، ويكون التعقيد الزمني ثابتًا تقريبًا أي يصبح O(1)‎.

إعادة التقطيع

يزداد التعقيد الزمني عند زيادة قيمة معامل الحمولة عن القيمة المعرّفة له مسبقًا (القيمة الافتراضية لمعامل الحمولة هو 0.75)، ولتجاوز هذه المشكلة يُضاعف حجم المصفوفة وتقطَّع جميع القيمة مرة أخرى وتخزّن في المصفوفة الجديدة ذات الحجم المضاعف وذلك للإبقاء على قيمة منخفضة لمعامل الحمولة وللتعقيد الزمني.

تنفيذ عملية إعادة التقطيع

تجرى عملية إعادة التقطيع باتباع الخطوات التالية:

• يجري التحقق من قيمة معامل الحمولة عند إضافة عنصر جديد إلى جدول التقطيع.
• إن كانت قيمة معامل الحمولة أكبر من القيمة المعرفة مسبقًا (أو القيمة الافتراضية 0.75 إن لم تكن هناك قيمة معرّفة) نجري عملية إعادة التقطيع.
• ننشئ مصفوفة جديدة حجمها ضعف حجم المصفوفة السابقة.
• نتنقل عبر جميع العناصر في المصفوفة القديمة ونستدعي الدالة insert()‎ لكل عنصر حتى تدرج حميع العناصر في المصفوفة الجديدة ذات الحجم الأكبر.

أمثلة

تعرض الشيفرة التالية طريقة تنفيذ عملية إعادة التقطيع في لغة جافا:

import java.util.ArrayList; 

class Map<K, V> { 

	class MapNode<K, V> { 

		K key; 
		V value; 
		MapNode<K, V> next; 

		public MapNode(K key, V value) 
		{ 
			this.key = key; 
			this.value = value; 
			next = null; 
		} 
	} 

	// المصفوفة التي تخزّن فيها أزواج مفتاح-قيمة
    ArrayList<MapNode<K, V> > buckets; 

	// n - عدد الأزواج المخزّنة
	int size; 

    // b - حجم المصفوفة
	int numBuckets; 

	// القيمة الافتراضية لمعامل الحمولة
	final double DEFAULT_LOAD_FACTOR = 0.75; 

	public Map() 
	{ 
		numBuckets = 5; 

		buckets = new ArrayList<>(numBuckets); 

		for (int i = 0; i < numBuckets; i++) { 
			// null  تهيئة المصفوفة بقيم
			buckets.add(null); 
		} 
		System.out.println("HashMap created"); 
		System.out.println("Number of pairs in the Map: " + size); 
		System.out.println("Size of Map: " + numBuckets); 
		System.out.println("Default Load Factor : " + DEFAULT_LOAD_FACTOR + "\n"); 
	} 

	private int getBucketInd(K key) 
	{ 
		
        // استخدام دالة داخلية من صنف الكائن
		int hashCode = key.hashCode(); 

		// array index = hashCode%numBuckets 
		return (hashCode % numBuckets); 
	} 

	public void insert(K key, V value) 
	{ 
		// الحصول على الموقع الذي سيدرج العنصر فيه
		int bucketInd = getBucketInd(key); 

		// العقدة الأولى في ذلك الموقع
		MapNode<K, V> head = buckets.get(bucketInd); 

		// المرور على جميع العقد الموجودة في ذلك الموقع أولًا
        // وذلك للتحقق ممّا إذا كان المفتاح موجودًا بالفعل
		while (head != null) { 

			// تُحدّث القيمة إن كان المفتاح موجودًا
            // If already present the value is updated 
			if (head.key.equals(key)) { 
				head.value = value; 
				return; 
			} 
			head = head.next; 
		} 

		// عقدة جديدة مع مفتاح وقيمة
		MapNode<K, V> newElementNode = new MapNode<K, V>(key, value); 

		// العقدة الأولى في الموقع
		head = buckets.get(bucketInd); 
		
        // تُدرج العقدة الجديدة وذلك بجعلها عقدة الرأس
        // وتكون العقدة التالية لها هي عقدة الرأس السابقة
		newElementNode.next = head; 

		buckets.set(bucketInd, newElementNode); 

		System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n"); 

        // زيادة حجم المصفوفة عند إضافة زوج (مفتاح-قيمة) جديد إلى جدول التقطيع
		size++; 

		// حساب قيمة معامل الحمولة
		double loadFactor = (1.0 * size) / numBuckets; 

		System.out.println("Current Load factor = " + loadFactor); 

		// إن تجاوزت قيمة معامل الحمولة 0.75، تنفّذ عملية إعادة التقطيع
		if (loadFactor > DEFAULT_LOAD_FACTOR) { 
			System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR); 
			System.out.println("Therefore Rehashing will be done.\n"); 

			// إعادة التقطيع 
			rehash(); 

			System.out.println("New Size of Map: " + numBuckets + "\n"); 
		} 

		System.out.println("Number of pairs in the Map: " + size); 
		System.out.println("Size of Map: " + numBuckets + "\n"); 
	} 

	private void rehash() 
	{ 

		System.out.println("\n***Rehashing Started***\n"); 

		// تحوّل القائمة الحالية إلى قائمة مؤقتة
		ArrayList<MapNode<K, V> > temp = buckets; 

		// إنشاء قائمة جديدة حجمها ضعف حجم القائمة القديمة
		buckets = new ArrayList<MapNode<K, V> >(2 * numBuckets); 

		for (int i = 0; i < 2 * numBuckets; i++) { 
			// null تهيئة المصفوفة بقيم
            // Initialised to null 
			buckets.add(null); 
		} 
		// نحوّل الحجم إلى القيمة 0
        // ثم نمرّ على جميع العقد في القائمة الأصلية
        // وندرجها كلّها في القائمة الجديدة
		size = 0; 
		numBuckets *= 2; 

		for (int i = 0; i < temp.size(); i++) { 

			// رأس السلسلة في هذا الموقع
			MapNode<K, V> head = temp.get(i); 

			while (head != null) { 
				K key = head.key; 
				V val = head.value; 

				// استدعاء دالة الإدراج لكل عقدة في القائمة المؤقتة
                // فالقائمة الجديدة هي القائمة الأساسية
				insert(key, val); 
				head = head.next; 
			} 
		} 

		System.out.println("\n***Rehashing Ended***\n"); 
	} 

	public void printMap() 
	{ 

		// تحوّل القائمة الحالية إلى قائمة مؤقتة
		ArrayList<MapNode<K, V> > temp = buckets; 

		System.out.println("Current HashMap:"); 
		// المرور على جميع العقد وطباعة قيمها
		for (int i = 0; i < temp.size(); i++) { 

			// رأس السلسلة في هذا الموقع
			MapNode<K, V> head = temp.get(i); 

			while (head != null) { 
				System.out.println("key = " + head.key + ", val = " + head.value); 

				head = head.next; 
			} 
		} 
		System.out.println(); 
	} 
} 

public class GFG { 

	public static void main(String[] args) 
	{ 

		// إنشاء جدول التقطيع
		Map<Integer, String> map = new Map<Integer, String>(); 

		// إدراج العناصر 
		map.insert(1, "Geeks"); 
		map.printMap(); 

		map.insert(2, "forGeeks"); 
		map.printMap(); 

		map.insert(3, "A"); 
		map.printMap(); 

		map.insert(4, "Computer"); 
		map.printMap(); 

		map.insert(5, "Portal"); 
		map.printMap(); 
	} 
}

تعطي الشيفرة السابقة المخرجات التالية:

HashMap created
Number of pairs in the Map: 0
Size of Map: 5
Default Load Factor : 0.75

Pair(1, Geeks) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 1
Size of Map: 5

Current HashMap:
key = 1, val = Geeks

Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 2
Size of Map: 5

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks

Pair(3, A) inserted successfully.

Current Load factor = 0.6
Number of pairs in the Map: 3
Size of Map: 5

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A

Pair(4, Computer) inserted successfully.

Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.


***Rehashing Started***

Pair(1, Geeks) inserted successfully.

Current Load factor = 0.1
Number of pairs in the Map: 1
Size of Map: 10

Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 2
Size of Map: 10

Pair(3, A) inserted successfully.

Current Load factor = 0.3
Number of pairs in the Map: 3
Size of Map: 10

Pair(4, Computer) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 4
Size of Map: 10


***Rehashing Ended***

New Size of Map: 10

Number of pairs in the Map: 4
Size of Map: 10

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer

Pair(5, Portal) inserted successfully.

Current Load factor = 0.5
Number of pairs in the Map: 5
Size of Map: 10

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer
key = 5, val = Portal

مصادر

• صفحة Load Factor and Rehashing في توثيق بنى المعطيات في موقع GeeksforGeeks.