We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Set implementations in all languages (that I know of) are hash tables, which does make lookup O(1) in the average case. The reason for this is that the memory allocated for the hash is indexed by the hash of the objects, so all the program has to do to know if the set contains an element is to generate the hash of that element and then jump directly to that location in memory (barring any collisions) and check if anything is there. For an array, the elements are not ordered in this way so the language has to iterate through (on average) half of the elements in the array if it contains the element and all of them if it doesn't. This is the reason hash lookups are faster. The downside is they require much more memory to store than an array, which is packed bytes.
Weighted Uniform Strings
You are viewing a single comment's thread. Return to all comments →
Set implementations in all languages (that I know of) are hash tables, which does make lookup O(1) in the average case. The reason for this is that the memory allocated for the hash is indexed by the hash of the objects, so all the program has to do to know if the set contains an element is to generate the hash of that element and then jump directly to that location in memory (barring any collisions) and check if anything is there. For an array, the elements are not ordered in this way so the language has to iterate through (on average) half of the elements in the array if it contains the element and all of them if it doesn't. This is the reason hash lookups are faster. The downside is they require much more memory to store than an array, which is packed bytes.