各种容器解析

来源:转载

1 容器分为两种:Collection和Map

2 各自旗下的子类关系:

Collection:

---- List:是一个接口,实现类有ArrayList/LinkedList/Vector.

特点:将以特定次序放入元素,取出来的可能和放进去的顺序不同。可以有重复元素。

---- Set:是一个接口,实现类有:HashSet/TreeSet.

特点:不能有重复元素,用它的迭代器来遍历元素。

用法:

-----ArrayList最长用,查找效率高。可以理解为以数组形式存储。LinkedList,可以理解为时以链表形式存储,插入删除效率高,查找效率低。虽然它也有get(int index)方法来得到元素,但内部是按照链表连接顺序来查找滴,因此get()的效率不高。Vector总是比ArrayList慢,很少使用。

-----HashSet:实际上是一个 HashMap 实例,从源码看出内部实例化的是一个hashMap.它不保证 set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 可以得到它的迭代器遍历元素。TreeSet:能够维护其内部元素的排序状态。通常只有当需要产生一个经过排序的序列才用TreeSet,它的查找删除效率都比HashSet低。更常用的是HashSet.

------TreeSet:是一个TreeMap的实例,保证排序后的顺序按升序排序,或者而按照set提供的比较器排序。

HashSet与TreeSet区别:前者无顺序,后者有顺序且不能重复。 HashSet是基于Hash算法实现的,其性能通常优于TreeSet,我们通常都应该使用HashSet,在我们需要排序的功能时,我门才使用TreeSet。

Map<K,V>:

-----是一个接口,实现类有HashMap/TreeMap/HashTable.

特点:存储的是一个键值对。“键”是独一无二滴,所对应的“值”可以重复。

用法:

---------HashMap:拥有增删查等基本操作,内部机制为利用对象的HashCode快速找到key.

注:HashMap利用了hash表的数据结构,通过一个自定的hash函数把关键字key转化为一个独一无二的int值,即hash值,用该数值确定该key在array数组(长度确定,默认为16,不能扩容,不同于ArrayList)中的位置,若该位置已经有值,则在位置后面连接一个链表,用来放有相同hash值的值,即一个array的值对应多个value.

附录:hash表结构还可以有别的方法来解决冲突,比如二次线性在散列等。详细略。

---------TreeMap:该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

---------HashTable:HashMap是用来代替HashTable的类,一般现在不用后者。后者不支持null值。hash值的使用不同,HashTable直接使用hashCode得到hash值,代码为:

int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap有个hash公式计算hash值,代码为

int hash = hash(k);int i = indexFor(hash, table.length);static int hash(Object x) { int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h;}static int indexFor(int h, int length) { return h & (length-1);}

HashMap用于快速查找。



分享给朋友:
您可能感兴趣的文章:
随机阅读: