java集合框架

Java 集合不存基本数据类型，而自动装箱机制可以方便我们转换

ArrayList<Integer> arr = new ArrayList<Integer>();

arr.add(1);

集合继承关系

Collection 为顶层接口

Collection接口有两个子接口List 和 Set
List有两个实现类 ArrayList 和 LinkedList
Set有两个实现类 HashSet 和 LinkedHashSet

Collection 接口

java.util.Collection;

Collection 表示容器对象，这些对象也称Collection元素

一些元素是允许有重复的，一些元素则不允许，一些元素是有序的，而另一些则无序

Collection 有很多的基本方法：

add(E e)

clear()

contains(Object o)

判断是否存在集合中

boolean remove(obj o)

删除元素（删除第一个出现）

size()

java中长度三种表现形式

数组.length 属性

字符串.length() 方法

集合.size() 方法

Object[] toArray()

集合转数组

Iterator

迭代器就是在做集合元素取出的一种标准

这是一种通用方式来完成：

判断集合中还有没有元素，如果有就取出来，没有就结束

boolean hasNext()

E next()

remove()

迭代器的使用方式：

Collection接口定义了一个接口方法，要求所有实现类重写：

Iterator iterator()

Iterator it = array.iterator(); // 创建迭代器

it.hasNext() // 调用迭代器方法

这就是一个很典型的，面向接口编程的思想体现！！

iterator 生成的是一个接口实现类对象，而使用者并不关心具体实现类是什么，只需要用接口接收即可

Collection<String> coll = new ArrayList<String>();
coll.add("123");
coll.add("5165465");
coll.add("dsvsdfvaebsd");
coll.add("dvadsvasdef");

Iterator<String> it = coll.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

迭代器并发修改异常

在遍历过程中发生集合的修改长度的情况

java.util.ConcurrentModificationException

增强for循环

JDK 1.5 新特性

JDK 1.5 出现新接口java.lang.Iterable从此Collection 开始继承 Iterable

该接口的作用就是能使用增强for循环写法foreach

所有继承的集合，包括数组，都可以用增强for

for(int i : array) {
    
}

增强for 没有索引，不能操作容器里边的元素

增强for本质上是迭代器，只是减少代码量了而已，其实最后还是转为迭代器代码

向下转型

如果不使用泛型，存储的元素将会被提升为Object

这是如果要使用元素的特有方法，就需要向下转型

因此建议使用时都加上泛型调用

Collection coll = new ArrayList();
coll.add("123");
coll.add("5165465");
coll.add("dsvsdfvaebsd");
coll.add("dvadsvasdef");

Iterator it = coll.iterator();
while (it.hasNext()) {
    String s = (String)it.next();
    System.out.println(s.length());
}

泛型引入

JDK 1.5 引入泛型，提高集合的安全性

Java泛型是伪泛型，是一个伪泛型，只是个编译手段，编译后的class文件，是不具有泛型的！

泛型类，泛型接口

泛型的定义

public class Generic<E> {
    public boolean add(E e) {
        element[size++] = e;
    }
}

泛型接口的实现

泛型调用者指定

public class ArrayList<E> implement Link<E> {
    
}

特写实现,调用者可以不用指定

public class ArrayList implement Link<String> {
    
}

泛型的通配

要求编写一个遍历所有集合的方法

public static void iterator(Collection<?> coll) {
    Iterator<?> it = coll.iterator();
    while(it.hasNext()){
        // it.next 获取得到的是Object类型
    }
}

这样通配得到的每个元素都变成Object类型，因此通配最好不要强转，否则还是会有没有引入泛型的弊端

泛型限定

? extends Person 上限限定，可以传递Person类的子类

? super Person 下限限定，可以传递Person类的父类

public static void iterator(Collection<? extends Person> coll) {
    Iterator<? extends Person> it = coll.iterator();
    while(it.hasNext()){
        // it.next 获取得到的是Person类型
    }
}

List 接口

list: 有序，索引，可重复

add(int index, E element)

给定位置插入元素，注意索引越界异常

E get(int index)

E remove(int index)

返回移除之前的元素

E set(int index, E element)

返回修改之前的元素

List存储结构

堆栈

先进后出

队列

先进先出

数组

查找快，增删慢

链表

编序不定，查找慢，增删快，不破坏原有的元素

arrayList 数组实现

线程不安全的

LinkedList 链表实现

单向链，线程也不安全

还大量提供了首尾操作方法

addFirst(E e)

addLast(E e)

getFirst()

getLast()

E removeFirst()

E removeLast()

pop()

push()

isEmpty()

Vector

线程安全的集合，是比较早期的方法JDK 1.0，现在基本已经被arrayList取代

Set存储结构

Set接口内容和Collection完全一样

HashSet == HashMap

内部实现直接用HashMap对象

哈希表实现，允许有null元素

存储取出都比较快，线程不安全

哈希表可以认为是链表和数组的结合体，数组记录的是链表表头的地址，通过某个哈希函数来确定元素放在数组的那个位置

桶的数量：是指数组单个元素上存放的链表元素的个数，因此哈希表的性能受到桶的数量的影响，一般出现这种情况是因为两个不同的元素在哈希函数的映射下到了同一个位置

初始容量：就是数组的初始容量，在java哈希表中默认是16，一般不要设定太高，会对性能有影响

加载因子：数组长度的百分比，在java中默认是0.75，意思是当数字长度达到12时，数组就要扩容了...
扩容到原来的两倍以上，扩容是一个很耗费资源的过程，这个动作又称为再哈希，加载因子太高，面对的冲突概率就越大，影响性能，加载因子太低，就还没怎么存就扩容了，浪费资源，当然也消耗性能！

对象的哈希值

hashCode()

Object 类的方法，返回的是对象的哈希值，结果是什么，不可预知，每次运行都不一样

对于String类，做了父类的重写，这样同一个字符串哈希值相同

String 的 hashCode算法：

public int hashCode() {
    int h = hash;
    if(h == 0 && value.length > 0) {
        char val[] = value;
        for(int i=0; i<value.length;i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

哈希表的存储过程

存储对象时，会先调用hashCode函数，得到哈希值
根据它内置的哈希函数，将该哈希值映射到数组的一个位置上
如果该位置上存在已有元素（冲突）那么又将调用equals函数判断该对象和该位置下各个对象是否相同
如果存在相同元素，则集合判定为相同，即舍去，如果不存在相同元素，才往后追加存储，采用桶的存储方式

具体源码是参考hashMap的put方法

对象的hashCode如何重写

假设有个Person对象，有两个属性name 和 age

public class Person {
    String name;
    int age;
}

为了让相同的name和age的人不存在哈希表的集合中去，应重写hashCode和equals方法，让它们返回的都相同

简单的hashCode重写

public int hashCode() {
    return name.hashCode() + age;
}

public boolean equals(Object obj) {
    if(this == obj) 
        return true;
    if(obj == null)
        return false
    if(obj instanceof Person) {
        Person p = (Person) obj;
        return name.equals(p.name) && age == p.age;
    }
    return false;
}

这样对于两个名字都为 “b”年龄都是10的人hashCode相同equals也相同，不会存在同一个hash集合中

但是对于名字“b”年龄10和名字“a”年龄11的人呢？它俩hashCode相同，只是equals不同，当然存在同个集合中了，但这增加了桶的数量

究其原因，我们要尽量降低hashCode相同的概率

参考String 的hashCode代码，可以看出通过一个乘积因子，可以在大概率上降低概率

比如将hashCode算法换为 name.hashCode() + age * 2

String 采用的是31，这也是通用的因子

但这也不能完全解决hashCode绝对不相同，比如重地和通话两个字符串，哈希值是相同的

public int hashCode() {
    return name.hashCode() + age * 31;
}

一般IDE会给我们自动生成hashCode算法，在它的算法里也是采用和String一样的套路

public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + age;
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

重写hashCode 和 equals重要性

判断元素存在依据是equals

List 集合判断元素存在可以调用contains方法，本质也是通过equals重写

Set 集合判断方式可以用add和contains两种方式

Java中的八大类型和包装类，都重写过hashCode和equals

LinkedHashSet

继承HashSet<E> 实现Set<E> 接口

具有可预知，迭代顺序的hashSet，也就是有序的，也是一个线程不安全的，运行效率高

内部实现维护着一个运行于有条目的双向链表

Map 接口

Map 接口是和Collection接口不同的存储形式，Map接口是以键值对方式存储，是一种双列集合

Map接口不能包含重复键，值可以重复

通常的Map集合为HashMap和LinkedMap

HashMap 采用的是哈希表的结构，存储顺序不能保证一致，为了保证键的唯一性，通常需要重写键的hashCode和equals

LinkedHashMap 其实是HashMap的子类，它可以保证存储顺序，通过哈希表+链表形式实现的

常用方法

V put(K, V)

public static void function() {
    Map<String, Integer> map = new Map<String, Integer>();
    
    map.put("a", 1);
    map.put("b", 1);
    map.put("g", 1);
    map.put("a", 5);
    // 存储重复键，会覆盖原有的值，这时候put 方法返回的是覆盖之前的值，否则为null
    System.out.println(map);
}

V get(K)

通过键返回值，如果不存在，返回null

V remove(K)

移除键，返回之前的值，如果不存在，返回null

Map遍历

Map集合的变量，比Collection复杂，一种方式获取所有键，遍历键值来拿到值

Set<K> keySet()

返回的是 java.util.HashMap$KeySet 内部类(HashSet)

Map<String, Person> map = new HashMap<String, Person>();
map.put("zz", new Person("zz", 13));
map.put("cc", new Person("cc", 44));
map.put("kk", new Person("kk", 12));
map.put("fr", new Person("fr", 17));

Set<String> st = map.keySet();
for (String key : st) {
    System.out.println(key + ":" + map.get(key));
}

是用增强for还可以简化为

for (String key : map.keySet()) {
    System.out.println(key + ":" + map.get(key));
}

Entry 接口

在Map方法的内部还定义了一个静态接口（内部接口），Entry

Set<Entry<K,V>> entrySet()

获取集合中的所有键值对

getKey()

获取该键值对的键

getValue()

获取该键值对的值

Set<Map.Entry<String, Person>> entrys = map.entrySet();

for (Map.Entry<String, Person> entry : entrys) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

简化为

for (Map.Entry<String, Person> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

Hashtable

Hashtable是一个线程安全的集合，运行速度慢，命运和Vector一样，JDK1.2开始逐渐被HashMap取代

HashMap允许存储null键，null值。而Hashtable不允许null

Hashtable的一个已知子类Properties还活跃着，和IO流有关

静态导入

JDK1.5 的新特性，一个好处就是减少代码量

能导入的，必须是静态的类或方法

import static java.lang.System.out;

out.println(key + ":" + map.get(key));

import static java.util.Arrays.sort;

sort(arr);

可变参数

JDK1.5 新特性可变参数前提是：类型确定，个数可以不定

可变参数的本质，就是数组

public static int getSum(int...a) {
    int sum = 0;
    for(int i: a) {
        sum += i;
    }
    sysout(a.length);
    return sum;
}

注意事项：

可变参数只能写一个

可变参数必须写在参数列表的最后

集合工具类Collections

都由静态方法组成

sort()

对List集合进行升序排列

int binarySearch(List<E>, E)

对List集合二分查找，必须是排好序的，返回的是一个索引，找不到返回负插入点-1

shuffle 随机排列

对List集合进行乱序排列

synchronized*

返回一个线程安全的集合，包括Collection和Map

对象比较器

实现Comparable<E>

实现Comparable<E> 接口可以让对象本身成为可比较对象

该接口下有一个compareTo方法，实现该方法进行比较

// 大于为正，等于为0，小于为负


public class Person implements Comparable<Person> {
    private String name;
    private int age;

    @Override
    public int compareTo(Person p) {
        // 大于为正，等于为0，小于为负
        return this.age - p.age;
    }
}

该对象即可使用集合工具类进行排序

List<Person> plist = new ArrayList<Person>();
plist.add(new Person("asdv", 20));
plist.add(new Person("dfvsegvf", 15));
plist.add(new Person("sdvdsew", 16));
plist.add(new Person("bdfngfdb", 13));

System.out.println(plist);

Collections.sort(plist);

System.out.println(plist);

实现Comparator<E>

实现Comparator<E>接口可以新定义一个比较器来比较两个对象

其中 E 指定的是比较对象的类型

该接口下有个compare方法，实现该方法对两个对象进行比较

public class PeopleComparator implements Comparator<People> {

@Override
public int compare(People p1, People p2) {
    // TODO Auto-generated method stub
    return p1.getAge() - p2.getAge();
}

}

这样对新定义比较器对象来说，在排序时指定比较器即可

Collections.sort(plist, new PeopleComparator());

List<People> plist = new ArrayList<People>();
plist.add(new People("asdv", 20));
plist.add(new People("dfvsegvf", 15));
plist.add(new People("sdvdsew", 16));
plist.add(new People("bdfngfdb", 13));
Collections.sort(plist, new PeopleComparator());
System.out.println(plist);

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,732评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,496评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,264评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,807评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,806评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,675评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,029评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,683评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,704评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,666评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,773评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,413评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,016评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,204评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,083评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,503评论 2赞 343