Insert is a bit trickier: we put x

Insert is a bit trickier: we put x in T1[h1(x)]. If there was some element y stored in that location, y must be evicted (thus the name "cuckoo" hashing). We put y in its other valid location T2[h2(y)]. If that location is occupied by some element z, we have to evict z and insert it in its other valid location T1[h1(z)]. We continue like this until we find an empty place and the process finishes, or until we give up because it starts to take too long (perhaps because we ran into a loop). If the latter happens, we conclude that insert failed, we stop and we rehash everything with new hash functions (increasing the table sizes if the tables are getting too full). It can be shown that insert takes constant time (on average), even if we account for the possible rehashing - assuming that the hash functions are sufficiently good.

ผลลัพธ์ (ไทย) 1:

แทรกอยู่เล็กน้อย trickier: เราใส่ x ใน T1[h1(x)] ถ้ามี y บางองค์ประกอบที่จัดเก็บในตำแหน่งที่ตั้ง y ต้องเอาออก (ดังนั้นชื่อ "cuckoo" hashing) เราใส่ y ในอื่น ๆ ถูกต้องสถาน T2[h2(y)] ถ้าตำแหน่งที่ว่าง โดย z บางองค์ประกอบ เราได้ขับไล่ z และแทรกในอื่น ๆ ถูกต้องสถานที่ T1[h1(z)] เราทำเช่นนี้จน กระทั่งเราพบสถานที่ว่างเปล่า และเสร็จสิ้นกระบวนการ หรือจน กว่าเราให้ขึ้น เพราะมันเริ่มจะยาวเกินไป (อาจจะ เพราะเราวิ่งมาวน) ถ้าจะเกิดขึ้น เราสรุปการแทรกที่ล้มเหลว เราหยุด และเรา rehash จึง มีฟังก์ชันแฮใหม่ (เพิ่มขนาดตารางถ้าตารางมีการเต็ม) มันสามารถแสดงแทรกที่ใช้เวลาคง (โดยเฉลี่ย), แม้เราบัญชีในที่สุด rehashing - สมมติว่าฟังก์ชันแฮชพอดี

ผลลัพธ์ (ไทย) 2:

แทรกเป็นบิต trickier: เราใส่ x ใน T1 [h1 (x)] ถ้ามีและองค์ประกอบบางอย่างที่เก็บไว้ในสถานที่และจะต้องถูกขับไล่ (ดังนั้นชื่อ "นกกาเหว่า" hashing) เราใส่และ T2 ในตำแหน่งที่ถูกต้องของอื่น ๆ [h2 (Y)] หากสถานที่ที่ถูกครอบครองโดย Z องค์ประกอบบางอย่างที่เราต้องขับไล่และ z ใส่ใน T1 ตำแหน่งที่ถูกต้องของอื่น ๆ [h1 (Z)] เรายังคงเช่นนี้จนกว่าเราจะหาสถานที่ที่ว่างเปล่าและเสร็จสิ้นกระบวนการหรือจนกว่าเราจะให้ขึ้นเพราะมันเริ่มที่จะใช้เวลานานเกินไป (อาจจะเพราะเราวิ่งเข้าไปในห่วง) ถ้าหลังที่เกิดขึ้นเราสรุปแทรกล้มเหลวเราหยุดและเราปรับปรุงใหม่ทุกอย่างที่มีฟังก์ชั่นใหม่ (การเพิ่มขนาดของตารางถ้าตารางจะได้รับเต็มรูปแบบมากเกินไป) มันจะแสดงให้เห็นแทรกที่ต้องใช้เวลาคงที่ (โดยเฉลี่ย) แม้ว่าเราบัญชีสำหรับ rehashing เป็นไปได้ - สมมติว่าฟังก์ชันแฮชที่ดีพอ

ผลลัพธ์ (ไทย) 3:

แทรกบิต trickier : เราใส่ T1 [ H1 x ( x ) ] หากมีบางองค์ประกอบและเก็บไว้ในสถานที่ที่ , และจะต้องถูกขับไล่ ( จึงชื่อ " กาเหว่า " hashing ) เราใส่ Y ในอื่น ๆที่ถูกต้องสถานที่ T2 [ H2 ( Y ) ] หากสถานที่ที่ถูกครอบครองโดยบางองค์ประกอบ Z , เราต้องขับไล่ Z และใส่มันในอื่น ๆที่ตำแหน่ง T1 [ H1 ( Z ) ] เราเป็นแบบนี้ต่อไป จนกว่าเราจะหาที่ว่างและกระบวนการเสร็จสิ้นหรือจนกว่าเราจะยอมแพ้ เพราะมันเริ่มจะยาวเกินไป ( อาจจะเพราะเราวิ่งเข้าไปในห่วง ) ถ้าหลังเกิดขึ้น เราสรุปได้ว่าแทรกล้มเหลว เราหยุด เราจะเปลี่ยนแปลงทุกอย่าง ด้วยฟังก์ชัน hash ใหม่ ( เพิ่มขนาดโต๊ะถ้าตารางจะได้รับเต็มด้วย ) มันสามารถแสดงให้เห็นว่าใส่ใช้เวลาคงที่ ( เฉลี่ย )ถ้าเราพิจารณาที่เป็นไปได้ rehashing - สมมติว่าฟังก์ชันที่ดีพอสมควร