网站建设实训作业,没有外贸网站 如果做外贸,烟台专业网站建设公司哪家好,WordPress书籍插件目录
第十二章 集合
学习目标
1. 集合框架的由来
2. 集合框架的继承体系
3. Collection接口
3.1 Collection接口的常用方法
4. Iterator接口
4.1 Iterator接口的抽象方法
4.2 获取迭代器接口实现类
4.3 迭代器的实现原理
4.4 并发修改异常
4.5 集合存储自定义对象并…目录
第十二章 集合
学习目标
1. 集合框架的由来
2. 集合框架的继承体系
3. Collection接口
3.1 Collection接口的常用方法
4. Iterator接口
4.1 Iterator接口的抽象方法
4.2 获取迭代器接口实现类
4.3 迭代器的实现原理
4.4 并发修改异常
4.5 集合存储自定义对象并迭代
5. List接口
5.1 List接口的特点
5.2 List接口自己的方法带有索引
5.3 List集合的特有迭代器
5.4 List接口的实现类的数据结构
6. ArrayList实现类
6.1 ArrayList集合的特点
6.2 ArrayList源码解析
6.2.1 ArrayList类的成员变量
6.2.2 ArrayList集合类的构造方法
6.2.3 ArrayList集合类的方法add()
7. LinkedList实现类
7.1 LinkedList集合的特点
7.2 LinkedList集合特有方法
7.3 LinkedList源码解析
7.3.1 LinkedList集合的成员变量
7.3.2 LinkedList集合的成员内部类Node结点
7.3.4 LinkedList集合的方法add()添加元素
7.3.5 LinkedList集合的方法get()获取元素
8. Set接口
8.1 Set集合存储和遍历
8.2 Set接口实现类HashSet类
8.3 对象的哈希值
8.4 String类的哈希值
8.5 哈希值的相关问题
8.6 哈希表的数据结构
8.7 哈希表存储对象的过程
8.8 哈希表存储自定义的对象
8.9 哈希表源码
8.10 哈希表面试的问题
9. 红黑树
9.1 TreeSet集合使用
9.2 TreeSet存储自定义对象
10. LinkedHashSet
11. Collections工具类
12. 泛型 Generic
12.1 泛型的安全机制
12.2 泛型中的 E 问题
12.3 自定义泛型类
12.4 泛型方法
12.5 泛型接口
12.6 泛型通配符
12.7 泛型限定
13. 增强型的for循环
13.1 for的格式
14. Map接口
14.1 Map接口方法
14.2 Map集合的遍历——键找值
14.3 Map集合的遍历——键值对映射关系
15. HashMap 实现类
16. Hashtable 实现类
17. LinkedHashMap 实现类
18. Vector 实现类
19. TreeMap 实现类
20. Properties 实现类 第十二章 集合
学习目标 认识集合框架 List集合的结构 ArrayList集合使用 ArrayList源码解析 LinkedList集合使用 LinkedList源码解析 对象的哈希值 哈希表数据结构 Collections工具类 了解泛型及其定义 哈希表确定对象唯一性 HashSet源码解析 红黑树结构Red/Black Tree Visualization 对象的自然顺序与比较器 1. 集合框架的由来
JDK1.2版本后出现这个集合框架到JDK1.5后大幅度优化。 集合本质上是存储对象的容器 数组也能存储对象数组弊端就是定长 解决数组的问题,开发出来集合框架集合框架无需考虑长度 集合和数组的区别与共同点 集合数组都是容器都可以存储数据 集合只存储引用数据类型不存储基本数据类型如int就会换成包装类Integer 数组可以存储基本类型也可以存储引用类型 数组定长集合容器变长
牢记数据多了存数组对象多了存集合 集合学习的关键点 怎么存储数据 怎么取出数据 选择哪种容器 2. 集合框架的继承体系 3. Collection接口
是所有单列集合的顶级接口任何单列集合都是他的子接口或者是实现类该接口中定义的方法是所有单列集合的共性方法。
CollectionE 尖括号就是泛型E我们要写,集合存储的数据类型
3.1 Collection接口的常用方法
方法的定义方法作用boolean add(E)元素添加到集合void clear()清空集合容器中的元素boolean contains(E)判断元素是否在集合中boolean isEmpty()判断集合的长度是不是0,是0返回trueint size()返回集合的长度,集合中元素的个数boolean remove(E)移除集合中指定的元素,移除成功返回trueT[] toArray(T[] a)集合转成数组
1 boolean add(E)
/**
* boolean add(E) 元素添加到集合中
* 返回值,目前都是true
*/
public static void collectionAdd(){//接口多态创建集合容器对象,存储的数据类型是字符串CollectionString coll new ArrayList();//集合对象的方法add添加元素coll.add(hello);coll.add(world);coll.add(java);coll.add(money);coll.add(wife);/*** 输出语句中,输出集合对象,调用的是方法toString()* 看到的内容是一个完整的字符串, 不叫遍历* 遍历时一个个过一个个输出*/System.out.println(coll);
} 2void clear()int size()boolean isEmpty() /*** void clear() 清空集合中的所有元素* int size() 集合的长度*/public static void collectionClear(){CollectionInteger coll new ArrayList();coll.add(1);coll.add(2);coll.add(3);System.out.println(coll);System.out.println(集合的长度:: coll.size());//长度coll.clear();System.out.println(coll);System.out.println(集合的长度:: coll.size());System.out.println(集合是空吗? coll.isEmpty());//长度0,isEmpty()返回true} 3boolean contains()boolean remove()
/*** boolean contains(E) 判断是否包含* boolean remove(E) 移除元素*/
public static void collectionContains(){//接口多态创建集合容器对象,存储的数据类型是字符串CollectionString coll new ArrayList();//集合对象的方法add添加元素coll.add(hello);coll.add(wife);coll.add(world);coll.add(java);coll.add(money);coll.add(wife);//判断集合中是否包含某个元素boolean b coll.contains(world);System.out.println(b b);//移除集合中的元素//删除成功返回true,如果有多个相同的对象,删除最先遇到的那个boolean b1 coll.remove(wife);System.out.println(b1 b1);System.out.println(coll);
} 4. Iterator接口
迭代器接口 Iterator为集合进行遍历的。迭代器技术是所有Collection集合的通用遍历形式。
4.1 Iterator接口的抽象方法 boolean hasNext() 判断集合中是否有下一个可以遍历的元素如果有返回true E next() 获取集合中下一个元素 void remove() 移除遍历到的元素
4.2 获取迭代器接口实现类
迭代器就是为了遍历集合而产生。集合的顶层接口Collection中定义了方法方法的名字就是 iterator()返回值是Iterator接口类型, 返回的是Iterator接口实现类的对象
Collection接口中的方法摘要 :public Iterator iterator() ; 返回迭代器接口实现类的对象使用的对象ArrayList,实现接口Collection,重写方法iterator();
public static void main(String[] args) {//迭代器遍历集合//接口多态创建集合容器对象,存储的数据类型是字符串CollectionString coll new ArrayList();//集合对象的方法add添加元素coll.add(hello);coll.add(world);coll.add(java);coll.add(money);coll.add(wife);//1 遍历 集合对象,调用方法iterator() 获取迭代器接口的实现类对象IteratorString it coll.iterator();//2 迭代器对象的方法,判断集合是否有下元素//boolean b it.hasNext();//System.out.println(b);//3 迭代器对象的方法,取出元素//String str it.next();//System.out.println(str);//条件,集合中有下一个元素就可以while ( it.hasNext() ){String str it.next();System.out.println(str);}
} 4.3 迭代器的实现原理
每个集合容器内部结构不同但是迭代器都可以进行统一的遍历实现
结论迭代器是隐藏在集合的内部的即为成员内部类提供公共的访问方式。
//Iterator接口的源码和ArrayList中的iterator的源码
interface Iterator{boolean hasNext();E next();void remove();
}public class ArrayList {public Iterator iterator(){return new Itr();}private class Itr implements Iterator{boolean hasNext(); //重写E next(); //重写void remove(); //重写}} 图1ArrayList的内部类实现接口Iterator的源码图片
4.4 并发修改异常
如何不发生这个异常
异常的产生原因在迭代器遍历集合的过程中使用了集合的功能改变了集合的长度造成。
public static void main(String[] args) {//迭代器遍历集合//接口多态创建集合容器对象,存储的数据类型是字符串CollectionString coll new ArrayList();//集合对象的方法add添加元素coll.add(hello);coll.add(world);coll.add(java);coll.add(money);coll.add(wife);//迭代器遍历集合IteratorString it coll.iterator();while ( it.hasNext() ){String str it.next();//判断,遍历到的集合元素是不是javaif (str.equals(java)){//添加元素 出现并发修改异常coll.add(add);}System.out.println(str);}
} 4.5 集合存储自定义对象并迭代
public static void main(String[] args) {//创建集合,存储自定义的对象CollectionPerson coll new ArrayList();//集合的方法add存储Person对象coll.add( new Person(张三,21) );coll.add( new Person(李四,22) );coll.add( new Person(王五,23) );//迭代器遍历集合IteratorPerson iterator coll.iterator();while (iterator.hasNext()){Person person iterator.next();System.out.println(person);System.out.println(person.getName());}
} /*** 定义私有成员* get set方法* 无参数构造方法** 满足以上的三个条件 ,这个类,换一个名字,叫JavaBean*/
public class Person {private String name;private int age;public Person(){}public Person(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return Person{ name name \ , age age };}
} 5. List接口
List接口继承Collection接口是单列集合。
5.1 List接口的特点 这个接口的集合都具有索引 这个接口中的元素允许重复 这个接口中的元素是有序的 元素不会排序 ,有序指的是 ,元素存储和取出的顺序是一致的 List接口的所有实现类都具有以上三个特征 5.2 List接口自己的方法带有索引
1void add(int index ,E e);
/**
* List接口的方法 add(int index, E e)
* 指定的索引位置,添加元素
*
* IndexOutOfBoundsException 集合越界异常 长度是size()
* StringIndexOutOfBoundsException 字符串越界异常 长度是 length()
* ArrayIndexOutOfBoundsException 数组越界异常 长度是 length
*/
public static void listAdd(){ListString list new ArrayList();list.add(a) ;//集合的尾部添加list.add(b);list.add(c);list.add(d);list.add(e);System.out.println(list);//指定的索引上,添加元素 ,3索引添加元素list.add(3,QQ);System.out.println(list);
} 2E get(int index); /*** List接口的方法 E get(int index)* 返回指定索引上的元素* List集合可以使用for循环像数组一样的方式遍历*/public static void listGet(){ListString list new ArrayList();list.add(a) ;//集合的尾部添加list.add(b);list.add(c);list.add(d);list.add(e);//List接口方法get取出元素//String s list.get(3);//System.out.println(s);for(int i 0 ; i list.size() ; i){System.out.println(list.get(i));}} 3E set(int index,E e); E remove(int index);
/*** List接口方法* E set (int index , E e) 修改指定索引上的元素,返回被修改之前的元素* E remove(int index) 移除指定索引上的元素, 返回被移除之前的元素*/public static void listSetRemove(){ListString list new ArrayList();list.add(a) ;//集合的尾部添加list.add(b);list.add(c);list.add(d);list.add(e);System.out.println(list);//修改指定索引上的元素,3索引String str list.set(3,https://www.baidu.com);System.out.println(list);System.out.println(str);//删除指定索引上的元素,删除3索引str list.remove(3);System.out.println(list);System.out.println(str);} 5.3 List集合的特有迭代器
List接口中的方法 listIterator() 返回迭代器迭代器的接口是ListIteratorList集合的专用迭代器。 ListIterator迭代器接口的方法 boolean hasNext() E next() boolean hasPrevious() 判断集合中是否有上一个元素,反向遍历 E previous() 取出集合的上一个元素 /*** List接口的方法:* listIterator() List集合的特有迭代器* 反向遍历*/public static void iterator(){ListString list new ArrayList();list.add(a) ;//集合的尾部添加list.add(b);list.add(c);list.add(d);list.add(e);//获取特有迭代器接口实现类对象ListIteratorString lit list.listIterator();//先要正向遍历while (lit.hasNext()){String s lit.next();System.out.println(s);}System.out.println();//判断上一个元素while (lit.hasPrevious()){//取出元素String s lit.previous();System.out.println(s);}} 5.4 List接口的实现类的数据结构
LinkedList链表 数组 : 有索引数组中元素的地址是连续查询速度快 数组的长度为固定新数组创建,数组元素的复制增删的效率慢 链表 链表没有索引采用对象之间内存地址记录的方式存储 查询元素,必须通过第一个节点依次查询查询性能慢 增删元素不会改变原有链表的结构,速度比较快 6. ArrayList实现类
6.1 ArrayList集合的特点
ArrayList类实现接口ListArrayList具备了List接口的特性 (有序重复索引) ArrayList集合底层的实现原理是数组,大小可变 (存储对象的时候长度无需考虑)。 数组的特点查询速度快增删慢。 数组的默认长度是10个每次的扩容是原来长度的1.5倍。 ArrayList是线程不安全的集合运行速度快。
6.2 ArrayList源码解析
6.2.1 ArrayList类的成员变量
private static final int DEFAULT_CAPACITY 10; //默认容量
private static final Object[] EMPTY_ELEMENTDATA {};//空数组
transient Object[] elementData; //ArrayList集合中的核心数组
private int size; //记录数组中存储个数
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8; //数组扩容的最大值
6.2.2 ArrayList集合类的构造方法
//无参数构造方法
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; //数组没有长度
//有参数的构造方法
public ArrayList(int 10) {if (initialCapacity 0) {//创建了10个长度的数组this.elementData new Object[10];} else if (initialCapacity 0) {this.elementData EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}
}
6.2.3 ArrayList集合类的方法add()
new ArrayList().add(abc); //集合中添加元素
public boolean add(abc) {//检查容量 (1)ensureCapacityInternal(size 1); //abc存储到数组中,存储数组0索引,size计数器elementData[size] abc;//数组扩容为10return true;
}
//检查集合中数组的容量, 参数是1
private void ensureCapacityInternal(int minCapacity 1) {//calculateCapacity 计算容量,方法的参是数组 , 1// ensureExplicitCapacity (10) 扩容的ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量方法, 返回10
private static int calculateCapacity(Object[] elementData, int minCapacity 1) {//存储元素的数组 默认的空的数组 构造方法中有赋值if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//返回最大值 max(10,1)return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}
//扩容
private void ensureExplicitCapacity(int minCapacity 10) {modCount;// 10 - 数组的长度0 0if (minCapacity - elementData.length 0)//grow方法(10) 数组增长的grow(minCapacity);
}
//增长的方法,参数是(10)private void grow(int minCapacity 10) {//变量oldCapacity保存,原有数组的长度 0int oldCapacity elementData.length; // 0//新的容量 老 (老的 / 2)int newCapacity oldCapacity (oldCapacity 1);// 0// 0 - 10 0 新容量-计算出的容量if (newCapacity - minCapacity 0)newCapacity minCapacity; //新容量 10//判断是否超过最大容量if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:
//数组的赋值,原始数组,和新的容量elementData Arrays.copyOf(elementData, newCapacity);} 7. LinkedList实现类
7.1 LinkedList集合的特点
LinkedList类实现接口ListLinkedList具备了List接口的特性 (有序重复索引) LinkedList底层实现原理是链表双向链表 LinkedList增删速度快 LinkedList查询慢 LinkedList是线程不安全的集合运行速度快
7.2 LinkedList集合特有方法
集合是链表实现可以单独操作链表的开头元素和结尾元素 void addFirst(E e) 元素插入到链表开头 void addLast(E e) 元素插入到链表结尾 E getFirst() 获取链表开头的元素 E getLast() 获取链表结尾的元素 E removeFirst() 移除链表开头的元素 E removeLast() 移除链表结尾的元素 void push(E e)元素推入堆栈中 E pop()元素从堆栈中弹出
public static void main(String[] args) {linkedPushPop();
}
//- void push(E e)元素推入堆栈中
//- E pop()元素从堆栈中弹出public static void linkedPushPop(){LinkedListString linkedList new LinkedListString();//元素推入堆栈中linkedList.push(a); //本质就是addFirst() 开头添加linkedList.push(b);linkedList.push(c);System.out.println(linkedList linkedList);String pop linkedList.pop(); // removeFirst()移除开头System.out.println(pop);System.out.println(linkedList linkedList);
}//- E removeFirst() 移除链表开头的元素
//- E removeLast() 移除链表结尾的元素
public static void linkedRemove(){LinkedListString linkedList new LinkedListString();linkedList.add(a); //结尾添加linkedList.add(b); //结尾添加linkedList.add(c); //结尾添加linkedList.add(d); //结尾添加System.out.println(linkedList linkedList);//移除开头元素,返回被移除之前String first linkedList.removeFirst();//移除结尾元素,返回被移除之前的String last linkedList.removeLast();System.out.println(first first);System.out.println(last last);System.out.println(linkedList linkedList);
}//- E getFirst() 获取链表开头的元素
//- E getLast() 获取链表结尾的元素
public static void linkedGet(){LinkedListString linkedList new LinkedListString();linkedList.add(a); //结尾添加linkedList.add(b); //结尾添加linkedList.add(c); //结尾添加linkedList.add(d); //结尾添加System.out.println(linkedList linkedList);//获取开头元素String first linkedList.getFirst();//获取结尾元素String last linkedList.getLast();System.out.println(first first);System.out.println(last last);System.out.println(linkedList linkedList);
}// void addFirst(E e) 元素插入到链表开头
// void addLast(E e) 元素插入到链表结尾
public static void linkedAdd(){LinkedListString linkedList new LinkedListString();linkedList.add(a); //结尾添加linkedList.add(b); //结尾添加linkedList.add(c); //结尾添加linkedList.add(d); //结尾添加System.out.println(linkedList linkedList);//结尾添加linkedList.addLast(f);linkedList.add(g);//开头添加linkedList.addFirst(e);System.out.println(linkedList linkedList);
}
7.3 LinkedList源码解析
7.3.1 LinkedList集合的成员变量
transient int size 0; //集合中存储元素个数计数器
transient NodeE first; //第一个元素是谁
transient NodeE last; //最后一个元素是谁
7.3.2 LinkedList集合的成员内部类Node结点
//链表中,每个结点对象
private static class NodeE {E item; //我们存储的元素NodeE next; // 下一个结点对象NodeE prev; // 上一个结点对象//构造方法,创建对象,传递上一个,下一个,存储的元素Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
7.3.4 LinkedList集合的方法add()添加元素
//添加元素 e 存储元素 abc
//再次添加元素 e
void linkLast(E abc) {//声明新的节点对象 lastfinal NodeE l last; // l null l abc节点//创建新的节点对象,三个参数, 最后一个对象,abc, 上一个对象nullfinal NodeE newNode new Node(l, e, null);//新节点赋值给最后一个节点last newNode;if (l null)//新存储的几点赋值给第一个节点first newNode;elsel.next newNode;size;modCount;
}
7.3.5 LinkedList集合的方法get()获取元素
//集合的获取的方法
//index是索引, size 长度计数器
NodeE node(int index) {//索引是否小于长度的一半,折半思想if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
} 8. Set接口
Set集合是接口Set继承Collection接口。Set集合不存储重复元素。
Set集合存储的数据是无序、不重复、无索引。 无序指的是存储和取出的顺序不一样但是由于使用迭代器遍历Set集合的输出会根据自然顺序输出例如“a”自然排序在“b”之前所以先输出“a”。 Set接口下的所有实现类都会具有这个特性。
Set接口的方法和父接口Collection中的方法完全一样。
8.1 Set集合存储和遍历 public static void main(String[] args) {//Set集合存储并迭代SetString set new HashSetString();//存储元素方法 addset.add(b);set.add(a);set.add(c);set.add(d);set.add(d);System.out.println(set set);IteratorString it set.iterator();while (it.hasNext()){System.out.println(it.next());}} 8.2 Set接口实现类HashSet类 HashSet集合类的特点 : 实现Set接口底层调用的是HashMap集合 HashSet的底层实现原理是哈希表 HashSet不保证迭代顺序元素存储和取出的顺序不一定 线程不安全运行速度快 图二创建HashSet其实就是创建HashMap
8.3 对象的哈希值
每个类继承Object类Object类定义方法
public native int hashCode(); // C语言编写,不开源 方法使用没有区别方法返回int类型的值,就称为哈希值 哈希值的结果不知道是怎么计算的调用toString()方法的时候返回的十六进制数和哈希值是一样的1b6d3586叫哈希值 (根本和内存地址是无关的) public static void main(String[] args) {Person p new Person();int code p.hashCode();// int 变量 460141958 (是什么,无所谓, 数字就是对象的哈希值)System.out.println(code);// com.atguigu.hash.Person1b6d3586System.out.println(p.toString());} 可以重写父类的hashCode()方法再输出该哈希值或toString()方法 /*** 重写父类的方法* 返回int值*/public int hashCode(){return 9527;} 8.4 String类的哈希值
字符串类重写方法hashCode()自定义了哈希值哈希值的计算方法是 h 31 * 上一次的计算结果 字符数组中元素的ASCII码值 *31 的目的减少相同哈希值的计算 String类的哈希值 //字符串String对象的哈希值private static void stringHash(){String s1 abc;String s2 abc;System.out.println(s1 s2); //T//String类继承Object,可以使用方法hashCodeSystem.out.println(s1.hashCode() s2.hashCode()); //T/*** String类继承Object类* String类重写父类的方法 hashCode() 自己定义了哈希值*/System.out.println(s1.hashCode());System.out.println(s2.hashCode());System.out.println();/*** 字符串内容不一样,有没有可能计算出相同的哈希值* String s1 abc;* String s2 abc;*/String s3 通话;String s4 重地;//1179395//1179395System.out.println(s3.hashCode());System.out.println(s4.hashCode());System.out.println(s3.equals(s4));} 8.5 哈希值的相关问题
问题 : ① 两个对象A、B 两个对象哈希值相同equals方法一定返回true吗? ② 两个对象A、B 两个对象equals方法返回true两个对象的哈希值一定相同吗
结论 : 两个对象的哈希值相同,不要求equals一定返回true. 两个对象的equals返回true,两个对象的哈希值必须一致
Sun 公司官方规定 : 上面的结论
8.6 哈希表的数据结构
数组 链表的组合体
class Node{E element; //存储的元素Node next; //下一个元素
}
main(){Node[] node new Node[5];
} 哈希表的底层数组长度默认是16个扩容为原来长度的2倍 加载因子默认是0.75F数组中存储元素的个数达到长度的75%就扩容 8.7 哈希表存储对象的过程
public static void main(String[] args) {SetString set new HashSetString();//存储对象set.add(abc);set.add(bbc);set.add(new String(abc));set.add(通话);set.add(重地);System.out.println(set set);
} 8.8 哈希表存储自定义的对象
需要重写自定义类的hashCode()和equal()两个方法
public class Student {private int age;private String name;public Student(){}public Student( String name,int age) {this.age age;this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;if (age ! student.age) return false;return name ! null ? name.equals(student.name) : student.name null;}Overridepublic int hashCode() {int result age;result 31 * result (name ! null ? name.hashCode() : 0);return result;}Overridepublic String toString() {return Student{ age age , name name \ };}
}
public static void main(String[] args) {SetStudent set new HashSetStudent();//存储Student的对象set.add(new Student(a1,201));set.add(new Student(a2,202));set.add(new Student(a2,202));set.add(new Student(a3,203));set.add(new Student(a4,204));System.out.println(set set);
}
8.9 哈希表源码
HashSet集合本身不具备任何功能内部调用了另一个集合对象HashMap
构造方法无参数
public HashSet() {map new HashMap();
}
HashMap类的成员变量
//哈希表数组的初始化容量,16
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 16
static final int MAXIMUM_CAPACITY 1 30; //最大容量
static final float DEFAULT_LOAD_FACTOR 0.75f;//价值因子
static final int TREEIFY_THRESHOLD 8;//阈值,转红黑树
static final int UNTREEIFY_THRESHOLD 6;//阈值,解除红黑树
static final int MIN_TREEIFY_CAPACITY 64;//阈值,转红黑树
HashMap内部类Node
//节点
static class NodeK,V implements Map.EntryK,V {final int hash; //对象哈希值final K key; //存储的对象V value; //使用Set的集合,value没有值NodeK,V next; //链表的下一个节点
} Set集合存储方法add()调用的是HashMap集合的方法put()【大致了解就行】
//HashMap存储对象的方法put,Key存储的元素,V是空的对象
public V put(K key, V value) {//存储值,传递新计算哈希值,要存储的元素return putVal(hash(key), key, value, false, true);
} //传递存储的对象,再次计算哈希值//尽量降低哈希值的碰撞
static final int hash(Object key) { int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
//存储值,重写计算的哈希值,要存储值
final V putVal(int hash, K key, V value, boolean false,boolean true) {//Node类型数组, Node类型数组 n, iNodeK,V[] tab; NodeK,V p; int n, i;//tab Node[]nullif ((tab table) null || (n tab.length) 0){//n赋值为 tab数组resize()方法返回数组,默认长度的数组16n (tab resize()).length;// 16//数组的长度-1 存储对象的哈希值,确定存储的位置//判断数组的索引上是不是空的if ((p tab[i (n - 1) hash]) null)//数组索引 赋值新的节点对象,传递计算的哈希值,存储的对象tab[i] newNode(hash, key, value, null);else{//数组的索引不是空,要存储的对象,已经有了//判断已经存在的对象,和要存储对象的哈希值和equals方法if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//遍历该索引下的链表,和每个元素比较hashCode和equals}}
}
8.10 哈希表面试的问题
JDK7版本和JDK8版本的哈希表的区别 JDK7没有转红黑树 JDK8转成红黑树 转成树的两个参数 当一个数组中存储的链表长度8 转树 数组的整体长度超过64 树转回链表 链表的长度 6 JDK7元素采用头插法JDK8元素采用尾插法 9. 红黑树
红黑树(Red-Black-Tree) 二叉树,本质就是链表 查询速度快 每个一个节点,只有两个子节点,左和右 树长偏了 自然平衡二叉树 二叉树的基础上,改进,保证树是平衡的 红黑树 每个节点有颜色,要么红,要么是黑 根节点必须是黑色 叶子节点必须是黑色 变量表示颜色,true黑色,false红色
9.1 TreeSet集合使用
TreeSet集合底层是红黑树结构依赖于TreeMap的实现
红黑树特点查找速度快线程不安全 可以对存储到红黑树的元素进行排序元素的自然顺序 abcd.. 字典顺序 public static void treeSetString(){SetString set new TreeSet();//存储元素set.add(abcd);set.add(ccdd);set.add(z);set.add(wasd);set.add(bbaa);System.out.println(set set);} 9.2 TreeSet存储自定义对象
/**
* TreeSet集合存储Student对象
*/
public static void treeSetStudent(){SetStudent set new TreeSetStudent();set.add(new Student(a,10));set.add(new Student(b,20));System.out.println(set set);
}
程序出现了异常类型的转换异常 ClassCastException
异常原因Student类不能进行类型的转换有接口没有实现java.lang.Comparable.
类实现接口Comparable这个类就具有了自然顺序。 Student类具有自然顺序 实现接口Comparable,重写方法compareTo /*** 重写方法compareTo* 返回int类型* 参数 : 要参与比较的对象* this对象和student对象** 红黑树,后来的对象是this,原有的对象是参数*/public int compareTo(Student student){return this.age - student.age;}自定义比较器 java.util.Comparator接口
/*** 自定义的比较器* 实现接口,重写方法*/
public class MyCom implements ComparatorStudent {Override/*** TreeSet集合自己调用方法* 传递参数* Student o1, Student o2* o1是后来的对象* o2是已经有的对象*/public int compare(Student o1, Student o2) {return o1.getAge() - o2.getAge();}
}
SetStudent set new TreeSetStudent( new MyCom()); 图三TreeSet集合的构造器 10. LinkedHashSet
底层的数据结构是哈希表继承HashSet
LinkedHashSet数据是双向链表有序的集合存储和取出的顺序一样
public static void main(String[] args) {SetString set new LinkedHashSet();set.add(b);set.add(e);set.add(c);set.add(a);set.add(d);System.out.println(set set);
} 11. Collections工具类 java.util.Collection 集合的顶级接口 java.util.Collections 操作集合的工具类 工具类的方法全部静态方法类名直接调用 主要是操作Collection系列的单列集合少部分功能可以操作Map集合
/*** 集合操作的工具类* Collections* 工具类有组方法: synchronized开头的** 传递集合,返回集合* 传递的集合,返回后,变成了线程安全的集合*/
public class CollectionsTest {public static void main(String[] args) {sort2();}//集合元素的排序,逆序public static void sort2(){ListInteger list new ArrayListInteger();list.add(1);list.add(15);list.add(5);list.add(20);list.add(9);list.add(25);System.out.println(list list);//Collections.reverseOrder() 逆转自然顺序Collections.sort(list,Collections.reverseOrder());System.out.println(list list);}//集合元素的排序public static void sort(){ListInteger list new ArrayListInteger();list.add(1);list.add(15);list.add(5);list.add(20);list.add(9);list.add(25);System.out.println(list list);Collections.sort(list);System.out.println(list list);}//集合元素的随机交换位置public static void shuffle(){ListInteger list new ArrayListInteger();list.add(1);list.add(15);list.add(5);list.add(20);list.add(9);list.add(25);System.out.println(list list);Collections.shuffle(list);System.out.println(list list);}//集合的二分查找public static void binarySearch(){ListInteger list new ArrayListInteger();list.add(1);list.add(5);list.add(9);list.add(15);list.add(20);list.add(25);int index Collections.binarySearch(list, 15);System.out.println(index);}
} 12. 泛型 Generic
泛型技术是JDK版本一大升级源自于JDK1.5
泛型就是集合类泛型
//无泛型写法
public static void main(String[] args) {/*** JDK没有泛型技术,就是这样写* 集合可以存储任何数据类型* 添加元素的数据类型是Object*/List list new ArrayList();list.add(a);list.add(1);Iterator it list.iterator();while (it.hasNext()){Object obj it.next();//不能类型转换System.out.println(obj);}
}
12.1 泛型的安全机制
软件升级安全性提高修复Bug错误改善用户体验增加功能,提升性能
JDK1.5里程碑版本
泛型作用强制了集合存储固定的数据类型
泛型的书写格式
集合类存储的数据类型 变量名 new 集合类存储的数据类型();类型可以不写:钻石操作符
加入泛型后程序的安全性提升了 public static void main(String[] args) {/*** JDK没有泛型技术,就是这样写* 集合可以存储任何数据类型* 添加元素的数据类型是Object*/ListString list new ArrayListString();list.add(a);list.add(1); //编译错误,数据类型不匹配IteratorString it list.iterator();while (it.hasNext()){String obj it.next(); //类型转换不需要System.out.println(obj);}} 使用泛型的好处 安全性提高了 程序的代码量减少 避免了类型的强制转换 程序的问题由运行时期提前到编译时期
12.2 泛型中的 E 问题
E没有什么实际价值只是一个变量而已
特殊等待接收指定的数据类型
//ArrayListE
//创建对象
ArrayListString al new ArrayListString();
//E 不在是E了,变成Stringpublic boolean add(String e) {}
12.3 自定义泛型类
/*** 定义类,类名叫工厂* 自定义泛型类* Factory什么都可以写 只是变量名而已*/
public class FactoryQQ {private QQ q;public void setQ(QQ q){this.q q;}public QQ getQ(){return q;}
}
public static void main(String[] args) {//创建对象Factory类对象// Factory factory new Factory();//没有泛型,QQ就是ObjectFactoryString factory new FactoryString();factory.setQ(abc);String s factory.getQ();System.out.println(s);FactoryDouble factory2 new FactoryDouble();factory2.setQ(1.5);Double q factory2.getQ();System.out.println(q);
}
12.4 泛型方法
/*** 泛型的方法,方法参数上*/
public class FactoryQ {/** 静态方法* Q是非静态的, Q的数据类型,是new的时候指定的** 静态方法参数中的泛型,不能和类一样* 静态方法的泛型,需要在方法上单独定义* 写在返回值类型的前面*/public static T void staticMethod(T q){System.out.println(q);}public void print(Q q){System.out.println(q);}
}
12.5 泛型接口 实现类实现接口不实现泛型 实现类实现接口同时指定泛型
//泛型接口
public interface Inter T {public abstract void inter(T t);
}/*** 实现接口,不理会泛型* 对象创建的时候,指定类型*/
public class InterImplT implements InterT{public void inter(T t){System.out.println(t);}
}
/*** 实现接口,同时指定泛型*/
public class InterImpl2 implements InterString {public void inter(String s) {System.out.println(ss);}
}
public class GenericTest {public static void main(String[] args) {InterString in new InterImplString();in.inter(ok);Inter in2 new InterImpl2();in2.inter(kkk);}
} 实现接口但是不实现泛型会在调用方法传入参数时才确认数据类型即参数类型会变成Object。 12.6 泛型通配符
指可以是任意引用类型
//泛型的通配符
public class GenericTest {public static void main(String[] args) {ListString stringList new ArrayListString();stringList.add(abc);stringList.add(bbc);ListInteger integerList new ArrayListInteger();integerList.add(1);integerList.add(2);each(stringList);each(integerList);}/*** 定义方法,可以同时迭代器 遍历这两个集合* 方法的参数,是要遍历的集合,不确定是哪个集合* 定义参数,写接口类型,不要写实现类*/public static void each(List? list){Iterator? it list.iterator();while (it.hasNext()){Object obj it.next();System.out.println(obj);}}
}
12.7 泛型限定
泛型限定限制的是数据类型 ? extends Company 传递类型可以是Company或者是他的子类 ? extends E传递E类型或者是E的子类泛型上限限定 ? super E 传递E类型或者是E的父类泛型下限限定
public static void main(String[] args) {//创建集合,存储员工对象//开发部的ListDevelopment devList new ArrayListDevelopment();//存储开发部员工对象Development d1 new Development();d1.setName(张三);d1.setId(开发部001);Development d2 new Development();d2.setName(张三2);d2.setId(开发部002);devList.add(d1);devList.add(d2);//财务部集合ListFinancial finList new ArrayListFinancial();Financial f1 new Financial();f1.setName(李四);f1.setId(财务部001);Financial f2 new Financial();f2.setName(李四2);f2.setId(财务部002);finList.add(f1);finList.add(f2);System.out.println(devList);System.out.println(finList);each(devList);each(finList);// ListInteger integerList new ArrayList();// integerList.add(1);// each(integerList);
}
/*** 要求 : 定义方法* 同时遍历2个集合* 遍历的同时取出集合元素,调用方法work()* ? 接收任何一个类型* 只能接收 Company和子类对象* 明确父类,不能明确子类*/
public static void each(List? extends Company list){Iterator? extends Company it list.iterator();while (it.hasNext()){//取出元素Company obj it.next();obj.work();}
} 13. 增强型的for循环
JDK1.5出现的特性循环的特性 (少些代码)
Collection是单列集合的顶级接口但是到JDK1.5后为Collection找了个爹
java.lang.Iterable接口实现接口就可以成为 foreach语句的目标
Collection、List、Set都继承了接口包括数组 Iterable接口定义了foreach()和iterator()两个方法
13.1 for的格式
for(数据类型 变量名 : 集合或者数组){} 遍历数组 /*** for循环遍历数组* for(数据类型 变量名 : 集合或者数组){}*/public static void forArray(){int[] arr {1,3,5,7,9};for(int i : arr){System.out.println(i1);}System.out.println(arrarr[0]);} 遍历集合 /* for循环遍历集合*/public static void forList(){ListString list new ArrayList();list.add(aaa);list.add(bbb);list.add(ccc);for(String s : list){System.out.println(s);}} 14. Map接口
java.util.Map接口是双列集合的顶级接口。
Map集合容器每次存储2个对象一个对象称为键(Key)一个对象称为值(Value)。 在一个Map的集合容器中键保证唯一性不包含重复键每个键只能对应一个值 14.1 Map接口方法 V put(K,V)存储键值对,存储重复键,返回被覆盖之前的值
/**
* put方法,存储键值对
* Map接口的实现类HashMap
*/
public static void mapPut(){//创建对象,指定键的数据类型,值的数据MapString,Integer map new HashMapString,Integer();map.put(a,1);map.put(b,2);map.put(c,3);map.put(d,4);
//相同键返回被覆盖的值Integer value map.put(c,5);System.out.println(map map);System.out.println(value value);
} V get(K)通过键获取值,参数传递键,找这个键对应的值,没有这个键返回null
/**
* V get(K)通过键获取值,参数传递键,找这个键对应的值,没有这个键返回null
*/
public static void mapGet(){//创建对象,指定键的数据类型,值的数据MapString,Integer map new HashMapString,Integer();map.put(a,1);map.put(b,2);map.put(c,3);map.put(d,4);//键找值Integer value map.get(f);System.out.println(value);
} boolean containsKey(K)判断集合是否包含这个键,包含返回true boolean containsValue(V)判断集合是否包含这个值,包含返回true int size() 返回集合长度,Map集合中键值对的个数 V remove(K)移除指定的键值对,返回被移除之前的值 CollectionV values() Map集合中的所有的值拿出,存储到Collection集合
/*boolean containsKey(K)判断集合是否包含这个键,包含返回true
- boolean containsValue(V)判断集合是否包含这个值,包含返回true
- int size() 返回集合长度,Map集合中键值对的个数
- V remove(K)移除指定的键值对,返回被移除之前的值
- CollectionV values() Map集合中的所有的值拿出,存储到Collection集合
*/
public static void mapMethod(){//创建集合,键是整数,值是StringMapInteger,String map new HashMapInteger, String();map.put(1,a);map.put(2,b);map.put(3,c);map.put(4,d);map.put(5,e);//boolean containsKey(K)判断集合是否包含这个键,包含返回trueboolean b map.containsKey(1);System.out.println(集合中包含键:b);//boolean containsValue(V)判断集合是否包含这个值,包含返回trueb map.containsValue(c);System.out.println(集合中包含值:b);//size()返回集合的长度int size map.size();System.out.println(集合长度:size);//V remove(K)移除指定的键值对,返回被移除之前的值String value map.remove(1);System.out.println(被删除之前的:value);System.out.println(map);//CollectionV values() Map集合中的所有的值拿出,存储到Collection集合CollectionString coll map.values();for(String s : coll){System.out.println(s);}
}
14.2 Map集合的遍历——键找值 实现思想 : Map接口定义了方法 keySet() 所有的键存储到Set集合 遍历Set集合 取出Set集合元素 Set集合的元素是Map集合的键 Map集合方法get()传递键获取值 /*** - Map接口定义了方法 keySet() 所有的键,存储到Set集合* - 遍历Set集合* - 取出Set集合元素 **Set集合的元素是Map集合的键*** - Map集合方法get()传递键获取值*/
public static void mapKeySet(){MapString,String map new HashMapString, String();map.put(a,java);map.put(b,c);map.put(c,php);map.put(d,python);map.put(e,erlang);//Map接口定义了方法 keySet() 所有的键,存储到Set集合SetString set map.keySet();//遍历Set集合IteratorString it set.iterator();//取出Set集合元素 **Set集合的元素是Map集合的键**while (it.hasNext()){String key it.next();//Map集合方法get()传递键获取值String value map.get(key);System.out.println(keyvalue);}
}
14.3 Map集合的遍历——键值对映射关系 实现思想 : Map接口的方法 Set Map.EntryKey,Value entrySet()【泛型可以多个表示】 方法返回Set集合集合中存储的元素比较特别 存储的是Map集合中键值对映射关系的对象内部接口 Map.Entry 遍历Set集合 取出Set集合的元素 是Map.Entry接口对象 接口的对象方法getKey()getValue() public static void mapEntrySet(){MapString,String map new HashMapString, String();map.put(a,java);map.put(b,c);map.put(c,php);map.put(d,python);map.put(e,erlang);//Map接口的方法 Set Map.EntryKey,Value entrySet()SetMap.EntryString,String set map.entrySet();//- 遍历Set集合IteratorMap.EntryString,String it set.iterator();while (it.hasNext()){//取出Set集合的元素Map.EntryString,String entry it.next();//- 接口的对象方法: getKey() ,getValue()String key entry.getKey();String value entry.getValue();System.out.println(key value);}} 15. HashMap 实现类 HashMap集合特点 是哈希表结构【Set和Map的底层数据结构都是是哈希表】 保证键唯一性用于键的对象必须重写hashCodeequals方法【伞公司写的hashCode方法不对外开放的所以不知道写了什么。但是能确定的一点是只要是桐哥类建立的对象他们的哈希值都是一样的。所以保证键唯一性需要重写hashCodeequals方法】 线程不安全集合运行速度快 集合运行使用null作为键或者值 /*** HashMap集合* 键是Person,值是String*/public static void hashMap2(){MapPerson,String map new HashMapPerson, String();map.put(new Person(a,20),广东);map.put(new Person(b,22),香港);map.put(new Person(b,22),贵港);map.put(new Person(c,24),澳门);map.put(new Person(d,26),深圳);System.out.println(map map);}/*** HashMap集合* 键是字符串,值是Person*/public static void hashMap1(){MapString, Person map new HashMapString, Person();map.put(a,new Person(张三,20));map.put(b,new Person(张三,20));map.put(c,new Person(张三,20));map.put(null,null);//SetString set map.keySet();for(String key : map.keySet()){//Person person map.get(key);System.out.println(keymap.get(key));}System.out.println();//SetMap.EntryString,Person set map.entrySet();for(Map.EntryString,Person entry : map.entrySet()){System.out.println(entry.getKey()entry.getValue());} 16. Hashtable 实现类
Map接口的实现类HashtableHashtable类诞生于JDK1.0版本Map接口诞生于JDK1.2版本。 Hashtable类从JDK1.2开始改进为实现Map接口。 Hashtable类的特点 底层数据结构是哈希表 线程安全的运行速度慢,被更加先进的HashMap取代 不允许null值null键存储null直接抛出空指针异常。 17. LinkedHashMap 实现类
LinkedHashMap继承HashMap实现Map接口LinkedHashMap底层实现原理是哈希表双向链存取有序。其它的特性和父类HashMap一样。
public static void main(String[] args) {MapString,String map new LinkedHashMapString, String();map.put(aa,qq);map.put(123,qq);map.put(bbb,qq);System.out.println(map);
} 18. Vector 实现类
List接口的实现Vector命运和Hashtable一样。 Vector类的特点 底层实现结构是数组 数组的默认容量是10每次扩容是原来的长度*2 线程安全运行速度慢被ArrayList取代 19. TreeMap 实现类 TreeMap集合的特点 底层实现是红黑树结构 (添加查询速度比较快) 存储到TreeMap中元素,对键进行排序 排序依据 : 对象的自然顺序,作为键的对象,实现了接口Comparable 自己提供比较器,实现接口Comparator,优先级高 线程不安全的,运行速度快 /*** TreeMap集合存储对象* Student作为键,字符串是值* 自定义的比较器排序*/public static void treeMap2(){MapStudent,String map new TreeMapStudent, String( new MyCom() );map.put(new Student(a,20),广东);map.put(new Student(b,19),广西);System.out.println(map map);}/*** TreeMap集合存储对象* Person作为键,字符串是值*/public static void treeMap1(){MapPerson,String map new TreeMapPerson, String();map.put(new Person(a,20),广东);map.put(new Person(b,19),广西);System.out.println(map map);}
/*** 自定义的比较器,实现接口 Comparator*/
class MyCom implements ComparatorStudent{/*** 方法compare 是TreeMap调用* 传递参数,后来的对象传递到s1, 已经有的对象传递到s2*/public int compare(Student s1, Student s2){return s1.getAge() - s2.getAge();}} /*** 进行比较:* compareTo方法由,集合TreeMap调用* 传递相关的参数 集合中后来的对象是this,先来的对象是参数 p*/public int compareTo(Person p){return this.age - p.age;} 20. Properties 实现类 Properties集合特点 继承Hashtable实现Map接口 底层是哈希表结构 线程是安全的,运行速度慢 集合没有泛型的写法键和值的数据类型锁定为String类型 集合有自己的特有方法 此集合可以和IO流对象结合使用实现数据的持久存储 方法和IO相关load(输入流) /*** 集合遍历* Properties类的方法 stringPropertyNames() [等效于map.keySet()] 返回Set集合* Set集合存储的是 Properties集合的所有键*/public static void prop3(){Properties prop new Properties();prop.setProperty(a,1);prop.setProperty(b,2);prop.setProperty(c,3);SetString set prop.stringPropertyNames();for(String key : set){System.out.println(key prop.getProperty(key));}}/*** 集合取出元素* Properties集合取出方法 getProperty(String key)*/public static void prop2(){Properties prop new Properties();prop.setProperty(a,1);prop.setProperty(b,2);prop.setProperty(c,3);System.out.println(prop);String value prop.getProperty(a);System.out.println(value);}/*** 集合存储键值对* Map接口,存储方法put* Properties集合存储方法 setProperty(String key,String value)*/public static void prop1(){Properties prop new Properties();prop.setProperty(a,1);prop.setProperty(b,2);prop.setProperty(c,3);System.out.println(prop);}
