用C實現(xiàn)關聯(lián)數(shù)組

Perlvim

C語言原生特性中沒有關聯(lián)數(shù)組，也稱字典，哈希，散列。但這是一種非常有用的數(shù)據(jù)類型。
通過對數(shù)組排序，二分法查找，和用關聯(lián)數(shù)組的查詢算法相比，哪個效率更高？
大家通常是怎么處理這個問題的？

linux_c_py_php

1, 排序: 假設數(shù)組已經(jīng)有序, 那么新插入元素也至少是lgn的.
2, 二分查找:  這和1是一碼事, 至少lgn的.
3, 哈希: O(1)的.

1和2本就是一碼事, 3通過擴容或者預分配足夠量的桶, 是可以保證常數(shù)查找速度.

Perlvim

你講的和代碼似的

yulihua49

Perlvim 發(fā)表于 2013-05-06 22:47
C語言原生特性中沒有關聯(lián)數(shù)組，也稱字典，哈希，散列。但這是一種非常有用的數(shù)據(jù)類型。
通過對數(shù)組排序，二 ...

這玩意本來和語言沒關系，是算法的范疇。