I would just like to add that the map implementation you have shown (which of course is a very simple one) is not O(1) for insert and lookup, as it might iterate the whole list whole finding a spot. This approach also requires a lot of work when removing items, as you have to fill gaps that might arise. But with a good hash function, maps of course can have an average case order of one, as collisions are rare compared to the number of items already in the map.
Hi Jan,
thank you for sharing yours insight here :)
I would just like to add that the map implementation you have shown (which of course is a very simple one) is not O(1) for insert and lookup, as it might iterate the whole list whole finding a spot. This approach also requires a lot of work when removing items, as you have to fill gaps that might arise. But with a good hash function, maps of course can have an average case order of one, as collisions are rare compared to the number of items already in the map.
Philip
Yeah, linear hashing is a simple but rather weak avoidance strategy.