首页 > 代码库 > Java数据结构
Java数据结构
本文借鉴优秀文章：http://blog.csdn.net/zhangerqing/article/details/8122075
数据结构：
下面的表格也许可以更直接的表现出他们之间的区别和联系：
接口 | 简述 | 实现 | 操作特性 | 成员要求 |
Set | 成员不能重复 | HashSet | 外部无序地遍历成员 | 成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 |
TreeSet | 外部有序地遍历成员；附加实现了SortedSet, 支持子集等要求顺序的操作 | 成员要求实现caparable接口，或者使用 Comparator构造TreeSet。成员一般为同一类型。 | ||
LinkedHashSet | 外部按成员的插入顺序遍历成员 | 成员与HashSet成员类似 | ||
List | 提供基于索引的对成员的随机访问 | ArrayList | 提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好 | 成员可为任意Object子类的对象 |
LinkedList | 对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差 | 成员可为任意Object子类的对象 | ||
Map | 保存键值对成员，基于键找值操作，compareTo或compare方法对键排序 | HashMap | 能满足用户对Map的通用需求 | 键成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 |
TreeMap | 支持对键有序地遍历，使用时建议先用HashMap增加和删除成员，最后从HashMap生成TreeMap；附加实现了SortedMap接口，支持子Map等要求顺序的操作 | 键成员要求实现caparable接口，或者使用Comparator构造TreeMap。键成员一般为同一类型。 | ||
LinkedHashMap | 保留键的插入顺序，用equals 方法检查键和值的相等性 | 成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 | ||
IdentityHashMap | 使用== 来检查键和值的相等性。 | 成员使用的是严格相等 | ||
WeakHashMap | 其行为依赖于垃圾回收线程，没有绝对理由则少用 |
|
一、HashMap的内部存储结构
Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表，数组的特点：连续空间，寻址迅速，但是在删除或者添加元素的时候需要有较大幅度的移动，所以查询速度快，增删较慢。而链表正好相反，由于空间不连续，寻址困难，增删元素只需修改指针，所以查询慢、增删快。有没有一种数据结构来综合一下数组和链表，以便发挥他们各自的优势？答案是肯定的！就是：哈希表。哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”，
二、ArrayList
ArrayList基于数组实现，所以它具备数组的特点，即查询速度较快，但是修改、插入的速度却有点儿慢，但是，下面将要介绍的LinkedList就是来解决这个问题的，LinkedList基于链表，与ArrayList互补，所以实际开发中我们应该按照自己的需求来定到底用哪一个。
三、LinkedList
LinkedList底层采用双向循环列表实现，进行插入和删除操作时具有较高的速度，我们还可以使用LinkedList来实现队列和栈。
四、WeakHashMap
理解该集合类之前，建议先去了解Java的垃圾回收机制，WeakHashMap多用于缓存系统，就是说在系统内存紧张的时候可随时进行GC，但是如果内存不紧张则可以用来存放一些缓存数据。因为如果使用HashMap的话，它里面的值基本都是强引用，即使内存不足，它也不会进行GC，这样系统就会报异
五、HashSet
Map ,Set 接口实现类 hashMap,HashSet最大的区别就是
hashMap 必须保持key 键 必须唯一 但存储的对象可以相同
HashSet 是存储接口也是基于hashMap，但是HashSet 的存储对象作为map.put()中的键，所以HashSet存储的对象必须唯一
六、Array 数组
java语言中，数组是一种最简单的复合数据类型。数组是有序数据的集合，数组中的每个元素具有相同的数据类型，可以用一个统一的数组名和下标来唯一地确定数组中的元素。数组有一维数组和多维数组。
(2). 既然ArrayList底层是用数组实现的，那么它和数组的区别在哪里？或者说最大的好处在哪里？
答：ArrayList底层是变长数组维护的，不需要定义其大小，如果长度不够了就会自动扩展为原来长度的一倍，数组的大小在定义的时候已经是个固定的值，不会自动扩展，数组的效率比集合的效率高，各有侧重点
最大的好处就是你不需要重新写个ArrayList,你需要数组的时候ArrayList提供toArray()是最快的
Eg: //String 复合数据类型
String[] array = new String[5];
array[0] = "a";
//对象复合数据类型
Father[] father = new Father[5];
father[0] = people;
//接口复合数据类型
Animal[] animal = new Animal[5];
List<Object> list = new ArrayList<>();
list.add("a");
list.add(5);
}
static interface Animal{
}
七、JAVA数据类型基础
简单数据类型包括：
整型(Interger): byte, short, int, long
浮点类型(Floating): float, double
字符类型(Textual): char
布尔类型(Logical): boolean
复合数据类型包括：
class
interface
数组
String
八、Queue 队列
简介
Queue是一种很常见的数据结构类型，在java里面Queue是一个接口，它只是定义了一个基本的Queue应该有哪些功能规约。实际上有多个Queue的实现，有的是采用线性表实现，有的基于链表实现。还有的适用于多线程的环境。java中具有Queue功能的类主要有如下几个：AbstractQueue,ArrayBlockingQueue, ConcurrentLinkedQueue, LinkedBlockingQueue, DelayQueue,LinkedList, PriorityBlockingQueue, PriorityQueue和ArrayDqueue。在本文中，我们主要讨论常用的两种实现：LinkedList和ArrayDeque。
(1) ArrayDeque
有了我们前面几篇分析的基础，我们可以很容易猜到ArrayDeque的内部实现机制。它的内部使用一个数组来保存具体的元素，然后分别使用head, tail来指示队列的头和尾。他们的定义如下：
Java代码
1. private transient E[] elements;
2.
3. private transient int head;
4.
5. private transient int tail;
6.
7. private static final int MIN_INITIAL_CAPACITY = 8;
ArrayDeque的默认长度为8，这么定义成2的指数值也是有一定好处的。在后面调整数组长度的时候我们会看到。关于tail需要注意的一点是tail所在的索引位置是null值，在它前面的元素才是队列中排在最后的元素。
Java数据结构