Java容器分类介绍

一，Java常见容器关系图

1、List集合的关系图

List接口下的实现类是基于数组或链表的实现。

Set接口下的实现类是基于HashMap中哈希表实现的，只是将value都置为空。

Java容器分类介绍

2、Map键值对

HashMap是线程不安全的，但是速度快。

HashTable是线程安全的，但是速度慢(因为增加了锁)。

LinkedHashMap是有序的，通过双重链表实现的。

TreeMap是按照key值进行排序的(默认自然顺序，可以通过自定义排序器)，底层实现是红黑树，不是哈希表机制。

Java容器分类介绍

二、深入分析HashMap与LinkedHashMap底层数据结构

1、HashMap是一个key唯一，无序，无理论是检索还是增删都是线性级别的容器。

ArrayList的底层是数组具有查询快，增删慢的特点。

LinkedList的底层是链表具有查询慢，增删快的特点。

如何才能产生一种既能保证查询速度又能保证增删速度的数据结构呢？

哈希表就是这样的一种数据结构：

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

结构图：

Java容器分类介绍

首先在new一个HashMap的时候会有一个initCapacity默认16 还有一个加载因子默认0.75 表明当map中长度大于长度的0.75倍后就会扩充HashMap的长度为当前的二倍。

HashMap是一个Entry[]。

我们通过结构图可以看出来，哈希表是由数组加链表组成，我们通过数组来存储指定哈希值下的Entry。

当不相等的两个key的hashcode值相等后，会调用equals方法。

通过这样的数据结构，不仅实现了快速查找(根据key的hashcode直接获取对应索引处的entry),而且因为是对应的地址，所以如果在删除时，直接将地址值置为null。

其中keySet与values是成员变量，我们在遍历的时候，直接调用即可。

2、LinkedHashMap是基于HashMap做了一个排序

排序的实现是模仿LinkedList通过链表去存储entry，所以我们叫双重链表结构。

结构图如下：

Java容器分类介绍

其他相关文章：

http://blog.****.net/duan19920101/article/details/51579136#reply