While reading the Lua source code, I learned that short string internalization is implemented using a hash table with open hashing, while the hash part of Lua tables uses closed hashing.
Both open hashing and closed hashing are implementation methods for hash tables, with the following characteristics:
- Open hash table: Uses linked list storage, doesn’t produce clustering, but increases space overhead due to additional pointer fields.
- Closed hash table: Uses sequential storage, more storage-efficient, but prone to clustering, harder to implement lookups, requires secondary probing.
- Overflow table: A combination of open and closed hashing - the first sequential table stores pointer-like fields, the second stores overflow.
For detailed descriptions of specific algorithms for open hashing, closed hashing, etc., please refer to the original article.
Original article: http://blog.csdn.net/u014613043/article/details/50726630
