如何使用数组设计获取、插入、删除的复杂度为O(1)的数据结构
How to use array to design a data structure that has O(1) for get, insert, delete
面试question:How使用数组设计数据结构，获取、插入、删除的复杂度为 O(1)？
我的想法是首先选择一个素数作为数组的大小，然后使用"mod by the size of array"作为一个简单的散列函数。对于数组中的每个点，我们存储一个链表来处理碰撞。
有没有更好的解决方案？
您提到的方法是 chaining 冲突解决技术，该技术在大多数实现中使用最广泛并且得到了实现。正如其他人评论的那样，几乎不可能实现保证 O(1) 获取、插入和删除的 HashMap。
此外，要实现仅包含数组的地图，您可以使用 open-addressing approach to collision resolution. It is a different collision resolution technique in which no pointers are used, just an array that is larger than the maximum number of elements that would ever be stored in the map. There are several ways for implementing open addressing based collision resolution, but the simplest of them all is the linear probing technique. You can read more about it's implementation here.
面试question:How使用数组设计数据结构，获取、插入、删除的复杂度为 O(1)？
我的想法是首先选择一个素数作为数组的大小，然后使用"mod by the size of array"作为一个简单的散列函数。对于数组中的每个点，我们存储一个链表来处理碰撞。
有没有更好的解决方案？
您提到的方法是 chaining 冲突解决技术，该技术在大多数实现中使用最广泛并且得到了实现。正如其他人评论的那样，几乎不可能实现保证 O(1) 获取、插入和删除的 HashMap。
此外，要实现仅包含数组的地图，您可以使用 open-addressing approach to collision resolution. It is a different collision resolution technique in which no pointers are used, just an array that is larger than the maximum number of elements that would ever be stored in the map. There are several ways for implementing open addressing based collision resolution, but the simplest of them all is the linear probing technique. You can read more about it's implementation here.