Dictionary,hashtable, stl:map有什么异同?

时间:2023-01-19 22:16:23

相同点:字典和map都是泛型,而hashtable不是泛型。

不同点:三者算法都不相同

Hashtable,看名字能想到,它是采用传统的哈希算法:探测散列算法,而字典则采用的是散列拉链算法,效率较高,空间也小。Stl:map使用的是红黑树算法,效率最低为o(nlogn)

这里要注意的是 dictionary使用的是拉链式哈希算法,在算法内部要对KEY进行哈希计算,即 comparer.GetHashCode(object o),就是说在C#中以值类型作KEY时(整形除外)都会发生装箱操作,

如以enum作key,是C#中造成GC ALLOC的典型原因。

注意数值类型(int, float, double等),int型作dictionary的key不会有GC ALLOC,这是因为c#有一个对应的重载,如comparer.GetHashCode(int key)的重载。

而其它类型则没有对应重载,自定义类型当然不会有对应重载了。