בעזרת Hash function אנו ממפים ערכים מטיפוס כלשהוא ArrayType
למספרים שלמים בתחום סופי(באותו סדר גודל של כמות הערכים)לפונקציה יכולים להיות התנגשויות כלומר יתכן ושני ערכים שונים
יעברו לאותו מספר, אבל בפונקציה טובה זה לא קורה הרבה(באותה
הסתברות שיהיו התנגשויות לו היינו מגרילים אקראית מספרים)
אנחנו ניצור עם כן טבלת ערבול, נבנה טבלה באותו הגודל של המערך
הראשון(לצורך העניין הקטן מבין השניים) ובתא הi בטבלה נשים
רשימה של כל האיברים מהמערך המקורי שערך הערבול שלהם הוא i
בממוצע אורך הרשימה הוא 1 ומשום שיש לנו פונקציית ערבול מוצלחת
רשימות ארוכות יהיו מאוד מאוד נדירות, הסיכוי לרשימה באורך מסוים
קטן באופן אקספוננציאלי, מכאן אין רשימות ארוכות. הכל זה 0,1,2 אולי 3
כעת כאשר אנו עוברים על המערך השני, ורוצים לבדוק האם ערך מסוים
היה קיים במערך הראשון אנחנו מחשבים את ערך הערבול שלו, מה שלוקח
זמן קבוע, ואז מסתכלים בטבלת הערבול רק על אותם איברים ספורים
שיש להם ערך ערבול כזה ומשווים, או שנמצא או שלא נמצא.
אנחנו בונים את הטבלה בO(N) זמן, ואז כל בדיקה האם איבר מסוים נמצא
לוקח O(1) מבצעים O(N) בדיקות כאלו.
ובסופו של דבר הכל ביחד לוקח O(N)
DRYICE