各种符号表实现的渐进性能总结

　　　　　　　　　　　　　　最坏情况下的成本　　　　　　　　　　　　　平均情况下的成本　　　　　　是否高效低支持有序性的相关操作　　　　　　关键接口

　　　　　　　　　　　　　　查找     　　插入　　　　　　　　　　　　　查找     　　插入

顺序查找（无序链表）　　　　　N 　　　　N　　　　　　　　　　　　　　N/2　　　　N　　　　　　　　　　否　　　　　　　　　　　　　　　　equals　　

二分查找（有序数组）　　　　　lgN　　　　2N　　　　　　　　　　　　　　lgN　　　N　　　　　　　　　　是　　　　　　　　　　　　　　　　　　compareTo

二叉树查找　　　　　　　　　　　N　　　　N　　　　　　　　　　　　　　1.39lgN　　1.39lgN　　　　　　　　是　　　　　　　　　　　　　　　　　　compareTo

2-3树查找（红黑树）　　　　　　2LgN　　　　2lgN　　　　　　　　　　1.00lgN　　　　1.00lgN　　　　　　是　　　　　　　　　　　　　　　　compareTo

拉链法（链表数组）　　　　　　<lg N　　　　<lgN　　　　　　　　　　N/(2M)　　　　　　N/m　　　　　　　是　　　　　　　　　　　　　　　　equals hascode　　

线性检测法（并行数组）　　　　clgN　　　　clgN　　　　　　　　　　<1.5　　　　　　<2.5　　　　　　　　　　是　　　　　　　　　　　　equals hascode

各种符号表实现的渐进性能总结

原文：http://www.cnblogs.com/ykong/p/4324703.html