Half year ago, I got a co-op opportunity in SAP. Once our group, 6 software developers, had lunch together, and the lead talk about a new grad he interviewed that morning, and said that girl did not answer well a question about hash table. Then, he asked me the same question: what is a hash table? I said: simply speaking, hash table is an array, plus listed list. Supprisely, our lead said: no, hash table is a map, and suggest me to get a newer data structure text book about.
After that, I did search new text books and online resource for hash table. And the result is still a little bit confusing. When developers use hash talbe containers, specally in perl, it really looks like a map, which contains [key, value] pairs. However, how is it implemented in low level? It’s still an array + linked list + hash function.
Hash table is not a standard contain in C++ STL now, but gcc and VC++ have already implemented it, and it will be in next version of STL standard (C++ TR1).
To make things more complicated, now people call it different name in different language. In STL, it has been call hash_map or unordered_map. In C#, Microsoft calls it “dicationary” container.
For most software developers, maybe they really don’t need to know the low-level different between hash table and map. But, if developers readlly want to make their program elegant and efficient, know more about the implementation is much helpful.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment