java基础系列－集合
最近复习了一下java中关于集合的一些知识点，写篇博客记录一下.
在java中提供的集合用来对对象进行统一的关联，它有三大接口
Collection,Map和Iterator，下面是一张集合相关类的结构图
看起来还是蛮复杂的，不过不是所有类都需要掌握，常用的也就那几个，下面介绍一些常用的集合类。分三块介绍，一部分是Collection这个接口，Collection包含List和Set,List下面有ArrayList,LinkedList,Vector. Set下面有HashSet,TreeSet,LinkedHashSet. 另外一部分是Iterator接口，最后一部分是Map接口一些实现类, HashMap,TreeMap,HashTable,LinedHashMap.
首先来看一下第一部分Collection中的List
Collection部分
List接口的特点
1，允许重复元素
2，必须是有序的
3，可以放入null元素
ArrayList特点
1，里面维护的是一个数组
2，默认数组长度是10
3，支持自动扩充，算法是（原数组长度＊3/2）＋1，大约是原数组长度一半左右.
4, 如果已知元素个数，可以使用指定初始容量的构造方法,这样可以有效避免扩充次数过多，从而提高效率.
5, 插入，删除，排序，效率比较低（因为内部实现使用数组）
6, 非线程安全
Vector特点
1，里面维护的是一个数组
2，默认数组长度是10
3，可以指定初始化容量
4, 扩充方式是如果有指定增量，扩充方式是当前容量加上指定增量，如果没有指定增量，扩充方式是原容量＊2
5，线程安全
LinkedList特点
1，内部以双向链表实现
2，删除和插入效率高
set接口的特点
1, 不包含重复元素
HashSet的特点
1，不保证迭代顺序
2，底层由HashMap实现
3，默认大小16
4，加载因子0.75
5，不包含重复元素（注意判断重复元素的依据是先验证hashcode, 如果相同再判断a1.equals(a2), 这是引用的比较。如果想判断对象内容是否重复，需要重写对象的equals方法，hashcode不同，那么它们一定不是同一个对象，hashcode相同那么它们不一定是同一个对象）
一个重写hashcode和equals的demo.
public class Person {
public String name;
public String number;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getNumber() {
return number;
}
public void setNumber(String number) {
this.number = number;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
if (name != null ? !name.equals(person.name) : person.name != null) return false;
return number != null ? number.equals(person.number) : person.number == null;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + (number != null ? number.hashCode() : 0);
return result;
}
}
TreeSet的特点
1，保证迭代顺序(并不是添加顺序,而是实现comparable接口)
2，底层由TreeMap实现
3，不能有重复的元素,这里也是利用comparable接口
public class Person implements Comparable<Person>{
public String name;
public String number;
public int age;
public Person(String name, String number, int age) {
this.name = name;
this.number = number;
this.age = age;
}
@Override
public int compareTo(@NonNull Person o) {
if (this.age > o.age){
return 1;
}else if (this.age < o.age){
return -1;
}else {
if (this.name.equals(o.name)){
return 0; //在TreeSet中return 0表示是重复元素
}else{
return -1;
}
}
}
}
LinkedHashSet的特点
1,添加顺序就是什么顺序
2,使用哈希表加双向链表实现
3,底层使用LinkedHashMap实现
4,同时它还是HashSet的子类
Iterator接口的特点
1,所有集合实现了该接口
2,提供统一的迭代
public static void iterator(Collection<String> collection){
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()){
String next = iterator.next();
System.out.print(next);
}
}
ListIterator接口
1,继承自Iterator
2,主要给List使用
3,进行前后遍历
public static void listIterator(List<String> list){
ListIterator<String> iterator = list.listIterator();
//从前往后
while (iterator.hasNext()){
String next = iterator.next();
System.out.print(next);
}
//从后往前
while (iterator.hasPrevious()){
String previous = iterator.previous();
System.out.print(previous);
}
}
＃Map接口的特点
1,以key value的形式存储
2,key不允许重复
3,注意它没有实现Collection接口
HashMap的特点
HashMap的实现原理: 它会去创建默认大小为16的数组，加载因子为0.75的哈西表，当我们put一个entry的时候，会去计算这个entry的key的hashcode,然后除以数组长度（刚开始默认为16）,得到一个余数（hash值），然后根据余数去确定这个entry放大数组的哪个位置，同时entry还有个next引用用来构建数组中的链表（其实也就是说数组中每个元素也是一条链表），当这个数组容量超过数组长度＊加载因子后，会扩充2倍，然后进行从新散列.
1,可以使用null值和null键
2,哈西表＋链表实现,这样设计提高了取数据的性能
3,不保证顺序(因为会重新散列)
4,默认大小16，加载因子0.75
5,key对象的hashcode计算hash值
6,hash表重新散列，影响性能
7,每次重新散列，原来数组长度＊2
8,非线程安全
最后补充连个HashMap经常会出现的问题
问题一, HashMap中出现HashCode碰撞是怎么回事?
当我们自定义一个类的时候会去重写hashCode方法，在这种情况下hashCode的计算是自定义的，所以会出现hashCode相同的情况，但是在这种情况下我们也能进行正常的put和get,因为hashCode相同HashMap中get和put还会通过equels进行地址的比较去判断是否重复元素，具体可以看以下put和get代码
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//注意的地方
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//注意的地方
return e.value;
}
return null;
}
问题二, HashCode和identityHashCode的区别?
HashCode是对象内容的hash, identityHashCode是对象引用的hash. 具体可以参考:
http://blog.csdn.net/tbdp6411/article/details/46915981
HashTable的特点
1,不允许使用null值和null键（可以null键或null值）
2,默认大小11，加载因子0.75
3,线程安全
TreeMap的特点
1,基于红黑树实现
2,非线程安全
3,以key的自然顺序构建映射树
4,使用自定义对象作为key值的时候，该对象必须要实现comparable接口
LinkedHashMap的特点
1,添加顺序就是什么顺序
2,继承自HashMap
Map接口的三种迭代方式
HashMap<Integer,String> hashMap = new HashMap<>();
hashMap.put(1,"小红");
hashMap.put(2,"小明");
hashMap.put(3,"小白");
Set setEntry = hashMap.entrySet();
Iterator iteratorEntry = setEntry.iterator();
while (iteratorEntry.hasNext()){
Map.Entry entry = (Map.Entry) iteratorEntry.next();
System.out.print("key = "+entry.getKey()+" value = "+entry.getValue());
}
Set<Integer> setKey = hashMap.keySet();
Iterator<Integer> iteratorKey = setKey.iterator();
while (iteratorKey.hasNext()){
Integer key = iteratorKey.next();
System.out.print("key = "+key+" value = "+hashMap.get(key));
}
Collection<String> values = hashMap.values();
for (String value : values){
System.out.print("value = "+value);
}
