用C实现关联数组

Perlvim

C语言原生特性中没有关联数组，也称字典，哈希，散列。但这是一种非常有用的数据类型。
通过对数组排序，二分法查找，和用关联数组的查询算法相比，哪个效率更高？
大家通常是怎么处理这个问题的？

linux_c_py_php

1, 排序: 假设数组已经有序, 那么新插入元素也至少是lgn的.
2, 二分查找:  这和1是一码事, 至少lgn的.
3, 哈希: O(1)的.

1和2本就是一码事, 3通过扩容或者预分配足够量的桶, 是可以保证常数查找速度.

Perlvim

你讲的和代码似的

yulihua49

Perlvim 发表于 2013-05-06 22:47
C语言原生特性中没有关联数组，也称字典，哈希，散列。但这是一种非常有用的数据类型。
通过对数组排序，二 ...

这玩意本来和语言没关系，是算法的范畴。