כשכותבים בפייתון:

[maor650]

כשכותבים בפייתון:

'TypeError: unhashable type: 'list-למה בעצם הכוונה? מה עליי לעשות כדי לתקן את זה?
תודה לעונים.

 

[BravoMan]

שום דבר - אתה לא אמור לתקן את זה.

list הוא טיפוס מובנה ב-Python.
אין אפשרות לעשות לו hash כי זו לא ממש פעולה הגיונית עבור מבנה כזה.

אני מנחש שקיבלת את השגיאה כשניסית להכניס list בתור מפתח למילון.
בדיוק כתבתי על זה לטרול המתכנן בשרשור הקודם (זה שצירפת עליו PDF).

פעולת hash היא פעולה שמקצה לערך כלשהו (זה יכול להיות אובייקט, מחרוזת או כל דבר אחר שזה הגיוני עבורו) מזהה מספרי בגודל קבועה שהינו ייחודי (כמעת) לאותו ערך.

הניסוח שלי כנראה גרוע, אם אתה רוצה הגדרה מדויקת, היא נמצאת ב-Wikipedia.

אם אתה רוצה לדעת מה שמים במקום כדי לא לקבל את השגיאה, צרף את הקוד ואת מה שאתה מנסה לעשות.

 

[nocgod]

Hash היא פונקציה

בצורה תיאורתית היא חד-חד ערכית וחד כיוונית.
כלומר לאותו הערך A הhash תמיד יהיה אותו ה hash ותיאורתית לא קיים ערך אחר B אשר שונה מA שיקבל את אותו הhash.
מה שמיוחד בhash הוא חד כיווני מבחינה מתמטית אתה לא אמור להיות יכול לחזור מערך hash לערך ממנו הוא התקבל.
כמובן שהכל מבחינה תיאורתית - מבחינה מעשית לשתי ערכים שונים יכול להיות אותו ה hash (במקרים מאוד קיצוניים) אבל גם בזה כל מימושי הhashmap מטפלים באמצעות רשימות מקושרות
הפלוס של hashmap הוא שתאירותית זמן השליפה מhashmap הוא הזמן שלוקח לך לחשב hash של האובייקט, לרוב נחשב כזמן של O(1)zzz...

במקרה והבחור רוצה לבנות inverse hashmap, הוא יכול להשתמש בvalues בתור הkey ובkeys שמתאימים לvalue לאגד אותם לתוך set.
נשמע דפוק כשאני מתאר את זה ככה, אבל:

// normal map
HashMap<String, Integer>
// inverse map
HashMap<Integer, HashSet<String>>

 

[טרול המתכנן]

כמעט דבר מהאמור לעיל אינו נכון.

אבל אני אעיר רק על נקודה אחת:
"אבל גם בזה כל מימושי הhashmap מטפלים באמצעות רשימות מקושרות"

זה לא נכון בכלל, ובפרט לא נכון לפייתון

 

[nocgod]

תפתח את בראסארד בייבי...

מבחינה תיאורתית זמן הכנסה ושליפה מhashtable הוא זמן קבוע O של 1 - בפועל מדובר בזמן הכנסה והוצאה, בלי תלות בזמן hash function, אבל גם היא יכולה להיות בזמן קבוע.
פונקציית hash היא פונקציה חד כיוונית וחד חד ערכית (חד חד ערכיות לא תמיד - במציאות)
לגבי חד כיוונית... אני מפציר בך לבצע MD5 לסטרינג ולנסות לקבל את הסטרינג בחזרה...או SHA1...ספר לי איך היה...
לגבי החלק האחרון שלא נכון בכלל - אני מתקשר לבראסארד להגיד לו שאתה טוען שהוא טועה?

Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys. For example, if 2,500 keys are hashed into a million buckets, even with a perfectly uniform random distribution, according to the birthday problem there is a 95% chance of at least two of the keys being hashed to the same slot.
Therefore, most hash table implementations have some collision resolution strategy to handle such events. Some common strategies are described below. All these methods require that the keys (or pointers to them) be stored in the table, together with the associated values.

מה גם איך תסביר את הסיבה שבג'אווה כשאתה פותח HashTable אתה רואה שמדובר ברשימה מקושרת? וזה העתקה מהDocumentation של Java7
Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially.

לגבי המימוש בפייטון, אתה צודק - זה לא ככה - זה מטפל בcollision באמצעות הזזה לתא הבא לשיטה קוראים probing.

סתם להעשרה עצמית תיכנס
http://en.wikipedia.org/wiki/Hash_function
http://en.wikipedia.org/wiki/Hash_table
חבל סתם להתנגח בי כל הזמן טרולוש - לפחות תבדוק שאתה צודק.

 

[טרול המתכנן]

לא יודע מי זה בראסארד.

אם אני שומע ברסאנס, זה תופס?

 

[nocgod]

לא יודע מי זה גיליס בראסארד... אמרת הכל

 

[Desslok of Gamilon]

Hash היא בהגדרה פונקציה שאינה חד-חד ערכית לא בתיאוריה ולא בפרקטיקה, משום שהיא ממפה תחום רחב של אפשרויות אל טווח צר מאוד של תוצאות אפשריות.

 

[nocgod]

בתחלס חזרתי קצת על hash

ונכתב בבירור שזה לא חד חד ערכי. מצד שני אני מאמין שכל השאר נכון...מאוד. במקרה של פייתון משתמשים בprobes כאשר בגאווה משתמשים ברשימות מקושרות כדי לשמור מפתחות בעלות אותו חאש ועקב העובדה שהפונקציה היא לא חח"ע היא לא הפיכה.