TechCodeview

مقدمة للتجزئة في بنية البيانات:

التجزئة هي تقنية شائعة في علوم الكمبيوتر تتضمن تعيين مجموعات كبيرة من البيانات إلى قيم ذات طول ثابت. إنها عملية تحويل مجموعة بيانات ذات حجم متغير إلى مجموعة بيانات ذات حجم ثابت. إن القدرة على إجراء عمليات بحث فعالة تجعل التجزئة مفهومًا أساسيًا في هياكل البيانات.

ما هو التجزئة؟

يتم استخدام خوارزمية التجزئة لتحويل المدخلات (مثل سلسلة أو عدد صحيح) إلى مخرجات ذات حجم ثابت (يشار إليها برمز التجزئة أو قيمة التجزئة). يتم بعد ذلك تخزين البيانات واسترجاعها باستخدام قيمة التجزئة هذه كمؤشر في مصفوفة أو جدول تجزئة. يجب أن تكون دالة التجزئة حتمية، مما يضمن أنها ستنتج دائمًا نفس النتيجة لمدخل معين.

يتم استخدام التجزئة بشكل شائع لإنشاء معرف فريد لجزء من البيانات، والذي يمكن استخدامه للبحث بسرعة عن تلك البيانات في مجموعة بيانات كبيرة. على سبيل المثال، قد يستخدم متصفح الويب التجزئة لتخزين كلمات مرور موقع الويب بشكل آمن. عندما يقوم المستخدم بإدخال كلمة المرور الخاصة به، يقوم المتصفح بتحويلها إلى قيمة تجزئة ومقارنتها بقيمة التجزئة المخزنة لمصادقة المستخدم.

ما هو مفتاح التجزئة؟

في سياق التجزئة، مفتاح التجزئة (المعروف أيضًا باسم قيمة التجزئة أو رمز التجزئة) هو تمثيل رقمي أو أبجدي رقمي ذو حجم ثابت يتم إنشاؤه بواسطة خوارزمية التجزئة. ويتم استخلاصها من البيانات المدخلة، مثل سلسلة نصية أو ملف، من خلال عملية تعرف باسم التجزئة.

يتضمن التجزئة تطبيق دالة رياضية محددة على بيانات الإدخال، مما ينتج عنه مفتاح تجزئة فريد يكون عادةً بطول ثابت، بغض النظر عن حجم الإدخال. مفتاح التجزئة الناتج هو في الأساس بصمة رقمية للبيانات الأصلية.

يخدم مفتاح التجزئة عدة أغراض. يتم استخدامه بشكل شائع للتحقق من سلامة البيانات، حيث أن أي تغيير بسيط في البيانات المدخلة سيؤدي إلى إنتاج مفتاح تجزئة مختلف بشكل كبير. تُستخدم مفاتيح التجزئة أيضًا لاسترجاع البيانات وتخزينها بكفاءة في جداول التجزئة أو هياكل البيانات، لأنها تتيح عمليات البحث والمقارنة السريعة.

كيف يعمل التجزئة؟

يمكن تقسيم عملية التجزئة إلى ثلاث خطوات:

إنشاء مثيل في جافا

• الإدخال: يتم إدخال البيانات المراد تجزئتها في خوارزمية التجزئة.
• وظيفة التجزئة: تأخذ خوارزمية التجزئة بيانات الإدخال وتطبق وظيفة رياضية لإنشاء قيمة تجزئة ذات حجم ثابت. يجب تصميم دالة التجزئة بحيث تنتج قيم المدخلات المختلفة قيم تجزئة مختلفة، والتغييرات الصغيرة في المدخلات تنتج تغييرات كبيرة في المخرجات.
• الإخراج: يتم إرجاع قيمة التجزئة، والتي يتم استخدامها كمؤشر لتخزين أو استرداد البيانات في بنية البيانات.

خوارزميات التجزئة:

هناك العديد من خوارزميات التجزئة، ولكل منها مزايا وعيوب مميزة. تتضمن الخوارزميات الأكثر شيوعًا ما يلي:

• MD5: خوارزمية تجزئة مستخدمة على نطاق واسع تنتج قيمة تجزئة 128 بت.
• SHA-1: خوارزمية تجزئة شائعة تنتج قيمة تجزئة 160 بت.
• SHA-256: خوارزمية تجزئة أكثر أمانًا تنتج قيمة تجزئة 256 بت.

دالة تجزئة:

دالة التجزئة: دالة التجزئة هي نوع من العمليات الرياضية التي تأخذ مدخلاً (أو مفتاحًا) وتخرج نتيجة ذات حجم ثابت تُعرف باسم رمز التجزئة أو قيمة التجزئة. يجب أن تنتج دالة التجزئة دائمًا نفس رمز التجزئة لنفس الإدخال حتى تكون حتمية. بالإضافة إلى ذلك، يجب أن تنتج وظيفة التجزئة رمز تجزئة فريدًا لكل إدخال، وهو ما يُعرف باسم خاصية التجزئة.

هناك أنواع مختلفة من وظائف التجزئة، بما في ذلك:

طريقة التقسيم:

تتضمن هذه الطريقة تقسيم المفتاح على حجم الجدول وأخذ الباقي كقيمة تجزئة. على سبيل المثال، إذا كان حجم الجدول 10 والمفتاح 23، فستكون قيمة التجزئة 3 (23% 10 = 3).

طريقة الضرب:

تتضمن هذه الطريقة ضرب المفتاح بثابت وأخذ الجزء الكسري من المنتج كقيمة التجزئة. على سبيل المثال، إذا كان المفتاح 23 والثابت هو 0.618، فستكون قيمة التجزئة 2 (floor(10*(0.61823 - Floor(0.61823))) = Floor(2.236) = 2).

التجزئة العالمية:

تتضمن هذه الطريقة استخدام دالة تجزئة عشوائية من عائلة وظائف التجزئة. وهذا يضمن أن وظيفة التجزئة ليست متحيزة تجاه أي مدخلات معينة ومقاومة للهجمات.

مفتاح الإضافية

حل التصادم

أحد التحديات الرئيسية في التجزئة هو التعامل مع التصادمات، والتي تحدث عندما تنتج قيمتان أو أكثر من قيم الإدخال نفس قيمة التجزئة. هناك تقنيات مختلفة تستخدم لحل التصادمات، بما في ذلك:

• التسلسل: في هذه التقنية، تحتوي كل فتحة جدول تجزئة على قائمة مرتبطة بجميع القيم التي لها نفس قيمة التجزئة. هذه التقنية بسيطة وسهلة التنفيذ، ولكنها قد تؤدي إلى ضعف الأداء عندما تصبح القوائم المرتبطة طويلة جدًا.
• العنونة المفتوحة: في هذه التقنية، عند حدوث تصادم، تبحث الخوارزمية عن فتحة فارغة في جدول التجزئة عن طريق فحص الفتحات المتعاقبة حتى يتم العثور على فتحة فارغة. يمكن أن تكون هذه التقنية أكثر كفاءة من التسلسل عندما يكون عامل الحمولة منخفضًا، ولكنها قد تؤدي إلى التجميع وضعف الأداء عندما يكون عامل الحمولة مرتفعًا.
• التجزئة المزدوجة: هذا هو شكل مختلف من العنونة المفتوحة التي تستخدم وظيفة تجزئة ثانية لتحديد الفتحة التالية التي يجب التحقيق فيها عند حدوث تصادم. يمكن أن تساعد هذه التقنية في تقليل التجميع وتحسين الأداء.

مثال على حل الاصطدام

دعنا نواصل مثالنا لجدول التجزئة بحجم 5. نريد تخزين أزواج القيمة الرئيسية 'John: 123456' و'Mary: 987654' في جدول التجزئة. ينتج كلا المفتاحين نفس رمز التجزئة وهو 4، لذلك يحدث تصادم.

يمكننا استخدام التسلسل لحل التصادم. نقوم بإنشاء قائمة مرتبطة في الفهرس 4 ونضيف أزواج القيمة الرئيسية إلى القائمة. يبدو جدول التجزئة الآن كما يلي:

0:

1:

charat java

2:

3:

4: يوحنا: 123456 -> مريم: 987654

5:

جدول التجزئة:

جدول التجزئة هو بنية بيانات تقوم بتخزين البيانات في مصفوفة. عادةً، يتم تحديد حجم للمصفوفة أكبر من عدد العناصر التي يمكن احتواؤها في جدول التجزئة. يتم تعيين المفتاح إلى فهرس في المصفوفة باستخدام وظيفة التجزئة.

يتم استخدام دالة التجزئة لتحديد موقع الفهرس الذي يجب إدراج العنصر فيه في جدول التجزئة لإضافة عنصر جديد. تتم إضافة العنصر إلى هذا الفهرس إذا لم يكن هناك تصادم. إذا كان هناك تصادم، فسيتم استخدام طريقة حل التصادم للعثور على الفتحة التالية المتاحة في المصفوفة.

يحتوي على بيثون

يتم استخدام وظيفة التجزئة لتحديد موقع الفهرس الذي تم تخزين العنصر فيه لاستعادته من جدول التجزئة. إذا لم يتم العثور على العنصر في هذا الفهرس، فسيتم استخدام طريقة حل التصادم للبحث عن العنصر في القائمة المرتبطة (إذا تم استخدام التسلسل) أو في الفتحة التالية المتاحة (إذا تم استخدام العنونة المفتوحة).

عمليات جدول التجزئة

هناك العديد من العمليات التي يمكن تنفيذها على جدول التجزئة، بما في ذلك:

• الإدراج: إدراج زوج جديد من قيمة المفتاح في جدول التجزئة.
• الحذف: إزالة زوج من القيمة الرئيسية من جدول التجزئة.
• البحث: البحث عن زوج من القيمة الرئيسية في جدول التجزئة.

إنشاء جدول التجزئة:

يتم استخدام التجزئة بشكل متكرر لإنشاء جداول التجزئة، وهي هياكل بيانات تتيح إدراج البيانات وحذفها واسترجاعها بسرعة. يمكن تخزين واحد أو أكثر من أزواج القيمة الرئيسية في كل صفائف من المجموعات التي تشكل جدول التجزئة.

لإنشاء جدول تجزئة، نحتاج أولاً إلى تحديد دالة تجزئة تقوم بتعيين كل مفتاح إلى فهرس فريد في المصفوفة. قد تكون وظيفة التجزئة البسيطة هي أخذ مجموع قيم ASCII للأحرف الموجودة في المفتاح واستخدام الباقي عند تقسيمه على حجم المصفوفة. ومع ذلك، فإن وظيفة التجزئة هذه غير فعالة ويمكن أن تؤدي إلى تصادمات (مفتاحان يرتبطان بنفس الفهرس).

لتجنب الاصطدامات، يمكننا استخدام وظائف تجزئة أكثر تقدمًا تنتج توزيعًا أكثر توازنًا لقيم التجزئة عبر المصفوفة. إحدى الخوارزميات الشائعة هي دالة التجزئة djb2، والتي تستخدم عمليات البت لإنشاء قيمة التجزئة:

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

تأخذ دالة التجزئة هذه سلسلة كمدخلات وترجع قيمة تجزئة عددية طويلة غير موقعة. تقوم الدالة بتهيئة قيمة تجزئة تبلغ 5381 ثم تتكرر على كل حرف في السلسلة، باستخدام عمليات البت لإنشاء قيمة تجزئة جديدة. يتم إرجاع قيمة التجزئة النهائية.

جداول التجزئة في C++

في لغة C++، توفر المكتبة القياسية فئة حاوية جدول التجزئة تسمى unordered_map. يتم تنفيذ الحاوية unordered_map باستخدام جدول التجزئة وتوفر وصولاً سريعًا إلى أزواج القيمة الرئيسية. تستخدم حاوية unordered_map دالة تجزئة لحساب رمز تجزئة المفاتيح ثم تستخدم العنونة المفتوحة لحل التصادمات.

لاستخدام حاوية unordered_map في C++، تحتاج إلى تضمين ملف الرأس. فيما يلي مثال لكيفية إنشاء حاوية unordered_map في لغة C++:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

توضيح:

جافا بول إلى السلسلة

• يوضح هذا البرنامج استخدام حاوية unordered_map في لغة C++، والتي يتم تنفيذها باستخدام جدول التجزئة ويوفر وصولاً سريعًا إلى أزواج القيمة الرئيسية.
• أولاً، يتضمن البرنامج ملفات الرأس الضرورية: و.
• بعد ذلك، يقوم البرنامج بإنشاء حاوية unordered_map فارغة تسمى my_map، والتي تحتوي على مفاتيح سلسلة وقيم عددية. يتم ذلك باستخدام بناء الجملة std::unordered_map my_map;
• بعد ذلك، يقوم البرنامج بإدراج ثلاثة أزواج من القيمة الرئيسية في حاوية my_map باستخدام عامل التشغيل []: 'apple' بقيمة 10، و'banana' بقيمة 20، و'orange' بقيمة 30.
• يتم ذلك باستخدام بناء الجملة my_map['apple'] = 10;, my_map['banana'] = 20;, وmy_map['orange'] = 30; على التوالى.
• أخيرًا، يقوم البرنامج بطباعة القيمة المرتبطة بالمفتاح 'banana' باستخدام عامل التشغيل [] والكائن std::cout.

مخرجات البرنامج:

إدراج البيانات في جدول التجزئة

لإدراج زوج من القيمة الرئيسية في جدول التجزئة، نحتاج أولاً إلى استخدام فهرس في المصفوفة لتخزين زوج القيمة الرئيسية. إذا تم تعيين مفتاح آخر لنفس الفهرس، فسنواجه تصادمًا ونحتاج إلى التعامل معه بشكل مناسب. إحدى الطرق الشائعة هي استخدام التسلسل، حيث تحتوي كل مجموعة في المصفوفة على قائمة مرتبطة بأزواج القيمة الرئيسية التي لها نفس قيمة التجزئة.

فيما يلي مثال لكيفية إدراج زوج من القيمة الرئيسية في جدول التجزئة باستخدام التسلسل:

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

توضيح:

• أولاً، يتم تعريف بنية تسمى العقدة، والتي تمثل عقدة واحدة في جدول التجزئة.
• تحتوي كل عقدة على ثلاثة أعضاء: مفتاح char* لتخزين المفتاح، وقيمة int لتخزين القيمة المرتبطة، ومؤشر إلى عقدة أخرى تسمى بجوار التعامل مع التصادمات في جدول التجزئة باستخدام قائمة مرتبطة.
• تم الإعلان عن مصفوفة من مؤشرات العقد تسمى hash_table بحجم 100. سيتم استخدام هذه المصفوفة لتخزين عناصر جدول التجزئة.
• تأخذ وظيفة الإدراج مفتاح char* وقيمة int كمعلمات.
• يبدأ الأمر بحساب قيمة التجزئة للمفتاح المحدد باستخدام وظيفة التجزئة، والتي من المفترض أن يتم تعريفها في مكان آخر من البرنامج.
• يتم بعد ذلك تقليل قيمة التجزئة لتلائم حجم مصفوفة hash_table باستخدام عامل المعامل % 100.
• يتم إنشاء عقدة جديدة باستخدام تخصيص الذاكرة الديناميكية (malloc(sizeof(node)))، ويتم تعيين أعضائها (المفتاح والقيمة والتالي) بالمفتاح المقدم والقيمة وNULL، على التوالي.
• إذا كانت الفتحة المقابلة في مصفوفة hash_table فارغة (NULL)، مما يشير إلى عدم حدوث تصادم، فسيتم تعيين العقدة الجديدة لتلك الفتحة مباشرة (hash_table[hash_value] = new_node).

ومع ذلك، إذا كانت هناك عقدة موجودة بالفعل في هذا الفهرس في مصفوفة hash_table، فستحتاج الوظيفة إلى معالجة التصادم. يجتاز القائمة المرتبطة بدءًا من العقدة الحالية (hash_table[hash_value]) وينتقل إلى العقدة التالية حتى يصل إلى النهاية (curr_node->next != NULL). بمجرد الوصول إلى نهاية القائمة، يتم إلحاق العقدة الجديدة باعتبارها العقدة التالية (curr_node->next = new_node).

تنفيذ التجزئة في C++:

دعونا نرى تنفيذ التجزئة في C++ باستخدام العنونة المفتوحة والفحص الخطي لحل التصادم. سنقوم بتنفيذ جدول التجزئة الذي يخزن الأعداد الصحيحة.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>