程序设计主要是数据结构+算法，而数据结构在面向对象思维里是“容器”的意思，数据结构主要负责数据的添加，删除，修改，查找及对数据的其他操作。编程里面对着不同问题场景，选择哪种数据结构进行操作就非常重要。试想：如果谷歌是以数组来存储数据的话，还会有那么快的搜索速度？所以下面就简单介绍java数据结构的体系和部分原理实现
总体思路：
- java集合体系结构图
- 集合父接口Collection，Map和集合工具类Collections
- List（列表）
- Set（规则集）
- Queue（队列
- Map(映射类)
java集合体系结构图
集合父接口Collection，Map和集合工具类Collections
Collection是java集合框架体系的总接口，其他集合框架都是实现Collection，封装了集合框架的公共操作：add（E），addAll（），remove（E），removeAll（），其方法摘要如下：
说到集合框架必须提到Collection的工具类Collections，它封装了所有集合的关于算法操作的具体实现静态方法：二分查找，找出集合最大值，集合最小值，打乱集合，以及生成不可修改集合，同步集合（多线程环境下使用），其主要方法API如下：
Collections的synchronizedCollection（）主要是在原来的方法外添加一个信号量来进行同步操作，其源码实现如下：
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
private static final long serialVersionUID = 3053995032091335093L;
final Collection<E> c; // Backing Collection
final Object mutex; // Object on which to synchronize
public boolean add(E e) {
//锁定信号量才可以对集合进行操作，在多线程环境下来进行同步,调用的还是原来的方法
synchronized (mutex) {return c.add(e);}
}
public boolean remove(Object o) {
//锁定信号量才可以对集合进行操作，在多线程环境下来进行同步,调用的还是原来的方法
synchronized (mutex) {return c.remove(o);}
}
}
集合框架Collection的三种主要实现如下：List(列表)，Set（散列集，有一个key-value的Map进行维护，其中key值保证Set集合里元素的唯一性），Queue（队列，先进先出，底层实现可以用List列表或者LinkedList链表）
集合框架的另外一种数据类型的总接口是Map，基于Key-Value进行存储数据的，其中Key键值是不可重复的，主要是通过类的hashCode()和equal()进行保证的
List（列表）
List列表允许存储相同元素，插入元素和按照下标获取元素方便，具体实现有ArrayList，LinkedList和Vector，
-
ArrayList底层基于数组实现的，按顺序存储元素以及快速按照元素下标进行获取元素，不可同步的；
-
而Vector底层也是数组，可进行同步操作，在多线程环境下可以使用；
-
LinkedList链表的具体机制如下图：可以在具体下标位置删除和添加元素，在许多需要根据具体下标添加和删除元素的应用场景下比ArrayList有更好的性能。
ArrayList和Vector的部分源码分析：
//ArrayList的add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//在数组结尾下标添加元素
elementData[size++] = e;
return true;
}
//ArrayList的remove()方法
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//获取移动的元素的个数
int numMoved = size - index - 1;
if (numMoved > 0)
//将移除元素的下标位置后的数组元素都往前移一位来填补空位，调用System.arraycopy方法调用虚拟机自带的方法进行操作效率更高
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//Vector添加了synchronized 进行同步
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
综上：Array List在不需要同步操作及不需要频繁删除任意下标的元素时推荐使用，Vector是在同步场景下使用，LinkedList是在需要频繁删除和添加任意下标的元素时使用
Set（规则集）
散列集，不能保证存储元素的顺序，保证存储元素的不可重复性。具体实现由HashSet，LinkedHashSet，TreeSet,
-
HashSet是哈希散列集，底层由HashMap支持的，主要使用hashCode()和equal()方法确保Key值不可重复性来保证元素的唯一性
-
LinkedHashSet底层由LinkedHashMap，则可以保证按照元素插入规则集的顺序进行提取。
-
TreeSet底层是由TreeMap支持的，可以按照Comparable接口对存储对象排序或者Comparator比较器接口进行存储对象的比较排序
HashSet的具体源码如下所示：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean contains(Object o) {
//判断是否存在元素就在hashMap中查看是否存在键值Key为元素o
return map.containsKey(o);
}
public boolean add(E e) {
//将要存储的元素当作hashMap的key值进行存储，保证存储元素的唯一性
return map.put(e, PRESENT)==null;
}
}
Queue（队列）
队列是一般按照先进先出First-In-First-Out的规则，元素被追加到队列末尾，在队列头进行删除，底层实现可以是数组，也可以是链表。主要实现有PriorityQueue和LinkedList,
-
其中PriorityQueue优先队列默认情况下以Comparable按照元素的自然顺序进行排序，最小值的元素优先级最高最先删除，也可以传入指定的比较器Comparator进行元素间的比较。
-
在java.util.concurrent包里有ArrayBlockingQueue，LinkedBlockingQueue等实现同步机制的队列数据结构，有兴趣可以查看源码进行研究。
##Map(映射类)
Map是按照Key-Value进行存储的数据结构，主要实现有HashMap,LinkedHashMap,TreeMap,
-
在不需要保证元素的顺序情况下，HashMap是非常高效的，主要是通过hashCode()和equal（）方法进行哈希化存储的，所以要求存储的对象要实现hashCode()和equal（）方法才能提高性能。HashMap具体的内部机制可以看
高爽|Coder的HashMap深度解析 -
而LinkedHashMap可以保证存储元素的顺序；可以按照元素的存储顺序或者元素的访问顺序进行排序存储，它的底层是由HashMap加上循环双向链表实现的。其中LinkedHashMap的具体机制可以看 LinkedHashMap及其源码分析
-
TreeMap在遍历排序好的键值是非常高效率的，默认是按照元素的实现Comprable接口方法进行排序的，也可以传入Comparator比较器接口进行比较排序
以下是TreeMap的put(K key, V value)源码分析
public V put(K key, V value) {
Entry<K,V> t = root;
//若集合为空，那么添加的元素成为TreeMap的根结点
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//当比较器存在时，使用比较器Comparator
if (cpr != null) {
do {
parent = t;
//使用比较器Comparator对元素的Key值进行比较
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {//当比较器不存在时，使用元素实现Comparable接口的方法
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
//使用元素实现Comparable接口的方法进行键值Key的比较
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
以上是最近学习整理的数据结构内容，对于数据结构的学习不单单需要知道各种数据结构的优缺点和应用场景，对于数据结构的源码和算法也是蕴含着很多可以学习的东西。数据结构在程序设计中的应用也非常广泛，比如Sturts的值栈机制就是使用List数据实现的，Mybatis的缓存机制就是使用Map机制进行实现的…
未来路还很长，继续前进
113
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
