问一道设计题： 用array 实现 类似HashSet/HashTable的Class

问一道面经题：

只使用array, 实现Add, Search, Clear O(1) time, Iterate O(N) time; N: 当前元素的个数。
不能使用 global version number.... 谢谢大家！


补充内容 (2017-6-23 11:17):
我打算用Linked list来存每个key的 hash code, object array来存KeyValuePair, 但到Delete时，怎么做到O(1) time呢？ 我的代码： http://www.evernote.com/l/AYGERZP0WVNCQo5elGynlhFApIjG09yfLEA/

补充内容 (2017-6-24 03:39):
我看的是面经，面的人用的是C++,提及过用random access array和sequential array来做...想了下sequential array, 比较贴近的也只有Linked List了。不知道这样理解有没有问题

要加个LinkedList的索引也可以吧.. 不过这只是心理上觉得是“exactly”O(N)舒服一点.. 实际用起来的时候，考虑到维护代价以及LinkedList本身的cache miss问题（这个在高性能系统中很重要），加这个索引可能反而会拖慢Iterate()的速度。

在OpenJDK7中HashMap的实现和Google densehash的实现中都是直接循环的：
hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/HashMap.java#l811
github.com/sparsehash/sparsehash/blob/master/src/sparsehash/internal/densehashtable.h#L181


那个Delete的问题还没有解决，具体是这样的：
-- 假设你有A, B, C三个元素都hash到10。现在按顺序插入了A, B, C，那么这三个元素将依次放在eleArr [10], [11], [12]。
-- 这时删除B，那么eleArr[11] = null
-- 紧接着Get C，那么你的Get会返回null，因为循环到eleArr[11]就停止了，然而C在eleArr[12]

你的代码是可行的，但是有两个地方需要修改：

(1) 去掉idxArr，然后在Iterate()的时候，暴力循环整个array。
-- 那么Iterate()的复杂度不就是O(capacity)而不是O(N)了吗？
-- 是的，但如果我们控制capacity <= c * N，c为某一常数，那么O(capacity)就等于O(N)

具体的方法就是根据HashTable中元素的数量动态扩展/收缩array的大小，这是一个经典的amortized analysis问题，你可以自己搜搜，我这边简单描述一下：
-- 初始capacity设为一个较小的数字，例如11（251也没问题，反正是常数）
-- 设定一个grow load factor（不妨命名为GLF），一般取值0.5
-- 设定一个shrink load factor（不妨命名为SLF），一般取值为1/4 * GLF，这里就0.125
-- 然后，用一个count成员变量记录HashTable中的元素数量。当count >= capacity * GLF时，扩展HashTable的大小约为原来2倍（建一个新的2倍大小的array替换原来的array，并重新插入所有元素）；当count < capacity * SLF时，收缩HashTable的大小为原来的1/2。

这样的HashTable有两个关键性质：
(A) 要么HashTable的capacity是初始值，要么其元素的数量介于[capacity * SLF, capacity * GLF]之间
(B) 扩展/收缩HashTable的代价均摊（amortize）到所有的Add/Delete操作中去后，是O(1)时间复杂度 -- 也就是说不用纠结于扩展/收缩的代价。

那么，循环一遍array的代价就是O(capacity) <= max(初始capacity, N / SLF) = O(N)

(2) 删除元素时不能简单地设置eleArr[hash] = null;


这个你可以google "open addressing hash table delete stack overflow"，就不具体展开了。


最后，你这个实现叫做Linear open addressing，OpenJDK7中HashMap的实现好像用的就是这个，然而在OpenJDK8中换成了Separate Chaining。
此外C++ std::unordered_map的底层实现也是Separate Chaining，比较奇葩的是google densehash，默认使用的Quadratic open addressing。

上面说的这些都可以搜到源代码，不过我的权限不能贴链接... 感兴趣你可以去搜搜看，如果想要深入掌握可以跟着写一遍Java的实现。

magicsets 发表于 2017-6-23 15:45
你的代码是可行的，但是有两个地方需要修改：

(1) 去掉idxArr，然后在Iterate()的时候，暴力循环整个arr ...

谢谢你的思路！

但是关于1的话，我有一个小疑问：因为题目要求的是严格的O(number of elements)，所以加个常数c的话 然后暴力遍历element array的话，虽说是O(c * #OfElement)，但这样会不会违反了这个规则？

我的思路是写一个Double Linked List来代替原来的Single Linked List, 然后每个HashEntry下面添加一个ListNode指针作为HashEntry的property。这样在删除的时候，我们只需要hash就能在Double LinkedList上定位到相应的Node, 此时只需要做常规的双链表删除Node的行为即可。
请问这种思路是否可行？！
更正后的代码：https://github.com/new2500/Misc/blob/master/O(1)%20map.cs

Update: 看了一下Delete的话，估计问题是不大的，因为这个O(1) map不是动态增长，如果设计成动态的话，的确是需要如你所说的需要counter，freeCount等元素来辅助增长。假设hash(x) =hash(y) = m的话。
Add method下面， 有eleArr[hash].key !=key 来确保 x和y存在不同的地方

在Delte上，我也相应添加了
        int hash = key % capacity;
        while (eleArr[hash].GetKey() != key)
        {
            hash = (hash + 1) % capacity;
        }
来确保当hash相同的时候，key也要相同来确定同一个元素。
后续就是直接删链表节点和set null。

Implement map using array? Only map’s operations are O(1).

顶一下！

题目里不是说"只使用array"么。implementation中用到Linked List没问题吗

stellari 发表于 2017-6-24 03:00
题目里不是说"只使用array"么。implementation中用到Linked List没问题吗

我看的是面经，面的人是C++,提及过用random access array和sequential array来做...想了下sequential array, 比较贴近的也只有Linked List了。
更正后的代码：https://github.com/new2500/Misc/blob/master/O(1)%20map.cs

magicsets 发表于 2017-6-24 07:08
要加个LinkedList的索引也可以吧.. 不过这只是心理上觉得是“exactly”O(N)舒服一点.. 实际用起来的时候， ...

我查了下Java的library, 感觉题目要求就是要实现一个LinkedHashMap呀。

magicsets 发表于 2017-6-24 07:08
要加个LinkedList的索引也可以吧.. 不过这只是心理上觉得是“exactly”O(N)舒服一点.. 实际用起来的时候， ...

我也觉得用Linked List这方法挺无赖的...但感觉这是最浅显的达到遍历时间是number of element 而不是length of array的做法..可能我没太get 到你的grow/shrink factor下达到number of element遍历时间的做法。
至于Delete的改进的话，我感觉只有一种做法：
删某个element时，使用一个DeletedEntry object来replace原来的HashEntry. 然后在add和get上面相应地添加上检查语句。

这种方法挺牺牲performance的，但对于open address的hash table来说，估计只有这条路了。根据题目提出的要求 一开始就不能用chainning的法子了。