JAVA集合那些事儿

今儿看网上阿里面经，感觉很多问了集合框架方面的知识，想来原来在公司的时候看过这方面的培训资料来着，赶紧瞅瞅。由于网上很多资料，总结的很经典了，这里只是对原理介绍一下，主要方便日后自己回顾。
 

从map说起吧，HashMap很经典了，自己的理解就是通过数组和链表实现的，hash算法最简单的理解就是取模，看源码可以知道HashMap内部有一个Entry[]的数组，而Entry本身的数据结构就是一个链表的节奏，差不多就是将key通过hash运算，在O(1)的时间里面确定要存在哪个Entry里面，就是等于确定Entry的下标，注意这里取的是key的hashCode()来进行计算，如果不重写hashCode()，则会默认调用父类Object的该方法，返回的是对象的内存地址。所以对于放入HashMap的对象一定要注意重写hashCode()方法，另外在存储的时候还会用到equals()方法所以务必同时重写hashCode()与equals()方法。贴个取值的代码:

        final Entry getEntry(Object key) {

　　int hash = (key == null) ? 0 : hash(key.hashCode());

　　for (Entry e = table[indexFor(hash, table.length)];

　　e != null;

　　e = e.next) {

　　Object k;

　　if (e.hash == hash &&

　　((k = e.key) == key || (key != null && key.equals(k))))

　　return e;

　　}

　　return null;

　　}

这里又要说下关于重写的时候的注意事项了，我们对同一个对象总是希望产生同一个hashCode值，前面说了不重写则返回的是内存地址，而每一次new对象的地址都是不一样的，因此hashCode最好是根据对象的不易变的唯一属性计算得出。比如汽车我们可用车牌号来唯一标识等。
 

HashMap差不多弄懂后，其他Map也就没什么了，LinkedHashMap保留了键的插入顺序，数组+双向链表实现。TreeHashMap则可以根据键排序，因为可以排序，自然需要键实现Comparable接口，底层通过红黑树实现。
 

HashSet通过HashMap实现，因为HashMap的键不重复，就和Set没有重复元素这一点完美契合，不用岂不浪费~
 

HashTable很重要的一个特性就是他是线程安全的，因此在实现的时候，方法基本都会加上synchronized关键字，自然这也会造成效率上的一定损失。另外一个线程安全的类是Vector向量。

先总结到这了。