อัพเกรดทักษะ Python ของคุณ: การตรวจสอบพจนานุกรม

ตารางแฮช (แผนที่แฮช) เป็นโครงสร้างข้อมูลที่ใช้ชนิดข้อมูลนามธรรมของอาร์เรย์ที่เชื่อมโยงซึ่งเป็นโครงสร้างที่สามารถแมปคีย์กับค่าได้

ถ้ามันมีกลิ่นเหมือนงูเหลือมdictให้ความรู้สึกเหมือน a dictและดูเหมือน ... อืมมันต้องเป็นdict. อย่างแน่นอน! โอ้และsetเช่นกัน ...

ฮะ?

พจนานุกรมและชุดใน Python ถูกนำไปใช้โดยใช้ตารางแฮช ในตอนแรกอาจฟังดูน่ากลัว แต่ในขณะที่เราตรวจสอบเพิ่มเติมทุกอย่างควรมีความชัดเจน

วัตถุประสงค์

ตลอดบทความนี้เราจะค้นพบวิธีการdictใช้งานa ใน Python และเราจะสร้างการใช้งาน (แบบง่าย) ของเราเอง บทความนี้แบ่งออกเป็นสามส่วนและการสร้างพจนานุกรมที่กำหนดเองจะเกิดขึ้นในสองส่วนแรก:

  1. ทำความเข้าใจว่าตารางแฮชคืออะไรและจะใช้อย่างไร
  2. ดำน้ำในซอร์สโค้ดของ Python เพื่อทำความเข้าใจวิธีการใช้งานพจนานุกรม
  3. สำรวจความแตกต่างระหว่างพจนานุกรมและโครงสร้างข้อมูลอื่น ๆ เช่นรายการและชุด

ตารางแฮชคืออะไร?

ตารางแฮชเป็นโครงสร้างที่ออกแบบมาเพื่อจัดเก็บรายการคู่คีย์ - ค่าโดยไม่ลดทอนความเร็วและประสิทธิภาพในการจัดการและค้นหาโครงสร้าง

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

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

ตรวจสอบให้แน่ใจว่าเราได้รวบรวมแนวคิดของตารางแฮชก่อนที่จะดำเนินการต่อ เราจะเริ่มต้นด้วยการสร้างโครงกระดูกสำหรับกำหนดเองที่เรียบง่าย (มาก) ของเราdictซึ่งประกอบด้วยวิธีการแทรกและการค้นหาเท่านั้นโดยใช้วิธีการดักฟังของ Python เราจะต้องเริ่มต้นตารางแฮชด้วยรายการขนาดเฉพาะและเปิดใช้งานการสมัครสมาชิก ([] sign) สำหรับมัน:

ตอนนี้รายการตารางแฮชของเราจำเป็นต้องมีโครงสร้างที่เฉพาะเจาะจงแต่ละรายการมีคีย์ค่าและแฮช:

ตัวอย่างพื้นฐาน

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

length of the employee's name % TABLE_SIZE

มากำหนดฟังก์ชันแฮชของเราในคลาส Entry:

ตอนนี้เราสามารถเริ่มต้นอาร์เรย์ 10 องค์ประกอบในตารางของเรา:

รอ! ลองคิดดู เราส่วนใหญ่จะจัดการกับการชนกันของแฮช ถ้าเรามีเพียง 10 องค์ประกอบมันจะยากกว่ามากสำหรับเราที่จะหาที่โล่งหลังการปะทะกัน มาตัดสินใจกันว่าตารางของเราจะมีขนาดเป็นสองเท่า - 20 องค์ประกอบ! มันจะมีประโยชน์ในอนาคตฉันสัญญา

ในการแทรกพนักงานแต่ละคนอย่างรวดเร็วเราจะปฏิบัติตามตรรกะ:

array[length of the employee's name % 20] = employee_remaining_sick_days

ดังนั้นวิธีการแทรกของเราจะมีลักษณะดังต่อไปนี้ (ยังไม่มีการจัดการการชนกันของแฮช):

สำหรับการค้นหาโดยทั่วไปเราจะทำเช่นเดียวกัน:

array[length of the employee's first name % 20] 

เรายังไม่เสร็จ!

การจัดการการชนกันของ Python

Python ใช้วิธีการที่เรียกว่า Open Addressing สำหรับจัดการการชนกัน นอกจากนี้ยังปรับขนาดตารางแฮชเมื่อถึงขนาดที่กำหนด แต่เราจะไม่พูดถึงแง่มุมนั้น เปิดคำจำกัดความที่อยู่จาก Wikipedia:

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

ลองตรวจสอบกระบวนการดึงค่าkeyโดยดูที่ซอร์สโค้ด Python (เขียนด้วย C):

  1. คำนวณแฮชของ key
  2. คำนวณindexรายการโดยโดยhash & maskที่mask = HASH_TABLE_SIZE-1(ในแง่ง่ายๆ - ใช้ N บิตสุดท้ายจากบิตแฮช):
i = (size_t)hash & mask;

3. หากว่างเปล่าให้ส่งกลับDKIX_EMPTYซึ่งแปลในที่สุดเป็นKeyError:

if (ix == DKIX_EMPTY) { *value_addr = NULL; return ix;}

4. ถ้าไม่ว่างให้เปรียบเทียบคีย์และแฮชและตั้งค่าที่value_addrอยู่เป็นที่อยู่ค่าจริงหากเท่ากัน:

if (ep->me_key == key) { *value_addr = ep->me_value; return ix;}

และ:

if (dk == mp->ma_keys && ep->me_key == startkey) { if (cmp > 0) { *value_addr = ep->me_value; return ix; }}

5. หากไม่เท่ากันให้ใช้แฮชที่แตกต่างกัน (อัลกอริทึมอธิบายที่นี่) และไปที่ขั้นตอนที่ 3 อีกครั้ง:

perturb >>= PERTURB_SHIFT;i = (i*5 + perturb + 1) & mask;

นี่คือแผนภาพเพื่อแสดงกระบวนการทั้งหมด:

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

ยืมแนวคิดจาก Python

เราสามารถยืมแนวคิดของ Python ในการเปรียบเทียบทั้งสองคีย์และแฮชของแต่ละรายการกับอ็อบเจ็กต์รายการของเรา (แทนที่วิธีก่อนหน้า):

ตารางแฮชของเรายังไม่มีการจัดการการชนกัน - มาใช้กันเถอะ! ดังที่เราเห็นก่อนหน้านี้ Python ทำได้โดยการเปรียบเทียบรายการแล้วเปลี่ยนมาสก์ของบิต แต่เราจะทำโดยใช้วิธีการที่เรียกว่าการตรวจสอบเชิงเส้น (ซึ่งเป็นรูปแบบของการกำหนดแอดเดรสแบบเปิดที่อธิบายไว้ข้างต้น):

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

So what we’re going to do is to move forward until we find an open space. If you recall, we implemented our table with double the size (20 elements and not 10) — This is where it comes handy. When we move forward, our search of an open space will be much quicker because there’s more room!

But we have a problem. What if someone evil tries to insert the 11th element? We need to raise an error (we won’t be dealing with table resizing in this article). We can keep a counter of filled entries in our table:

Now let’s implement the same in our searching method:

The full code can be found here.

Now the company can safely store sick days for each employee:

Python Set

Going back to the beginning of the article, set and dict in Python are implemented very similarly, with set using only key and hash inside each record, as can be seen in the source code:

typedef struct { PyObject *key; Py_hash_t hash; /* Cached hash code of the key */} setentry;

As opposed to dict, that holds a value:

typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */} PyDictKeyEntry;

Performance and Order

Time comparison

I think it’s now clear that a dict is much much faster than a list (and takes way more memory space), in terms of searching, inserting (at a specific place) and deleting. Let's validate that assumption with some code (I am running the code on a 2017 MacBook Pro):

And the following is the test code (once for the dict and once for the list, replacing d):

The results are, well, pretty much what we expected..

dict: 0.015382766723632812 seconds

list:55.5544171333313 seconds

Order depends on insertion order

The order of the dict depends on the history of insertion. If we insert an entry with a specific hash, and afterwards an entry with the same hash, the second entry is going to end up in a different place then if we were to insert it first.

Before you go…

Thanks for reading! You can follow me on Medium for more of these articles, or on GitHub for discovering some cool repos :)

If you enjoyed this article, please hold down the clap button ? to help others find it. The longer you hold it, the more claps you give!

And do not hesitate to share your thoughts in the comments below, or correct me if I got something wrong.

Additional resources

  1. Hash Crash: The Basics of Hash Tables
  2. The Mighty Dictionary
  3. Introduction to Algorithms