多維散列的空間複雜度

Question

我想存儲一個製表符分隔值的輸入，其中C1，C2，C3和C4代表數據的列，並且有N行數據。如果是這樣，我可以在散列中查找是否存在C1，C2，C3，C4的某些給定值。有人向我暗示，在最壞的情況下，這個空間複雜度是N 。我希望能夠幫助你明確解釋爲什麼這不是事實。

Answer 1

另一個人在想，如果你試圖存儲一個N乘N格的點數，那麼將有N個存儲點。

但是，如果你有N個點，那麼你只是存儲一個散列。具有N個數據點的散列通常需要O（N）空間。 （從技術上講，它需要散列表的大小加上數據的空間，但是人們通常動態地將散列表的大小設置爲與數據集相同的數量級大小。）