导图社区 3.JavaMap,Collection
javaMap知识整理,包括概念、Hash Map、Hsah Table、Tree Map等板块。
编辑于2022-04-01 14:07:25集合
map
概念
Map接口中存放的数据是以键值对的方式存在的的,
Map接口是无序的,跟添加的顺序是无关系的
map接口的泛型应该有两个
HashMap
存取数据过程
1.获得key对象的hashcode
首先调用ket对象的hashcode()方法,获得hashcdoe
2.根据hashcode计算出hash值(要求在[ 0 , 素组长度-1 ])区间
3.生成Entry对象
一个Entry对象包含4个部分:key对象,value值,hash值,指向下一个Entry对象的引用
4.将Entry对象放到table数组中
如果Entry对象对应的数组索引还没有存放entry对象,则直接将Entry对象存储进数组;如果对应索引位置已经有Entry对象,则将已有Entry对象的next指向本Entry对象,形成链表。
当添加一个元素(key-value)时,首先计算key的hash值,以此确定插入数组中的位置,但是可能存在同一个hash值的元素已经放在同一位置了,这是就添加到同一hash值元素的后面,他们在数组同一个位置,就形成了链表,同一个链表上的hash值是相同的,所以说数组存放的是链表。
扩容问题
HashMap的位桶数组,初始大小为16,如果位桶数组中的元素达到(0.75*数组length),就重新调整数组大小变为2的次幂
特点
底层数据结构有数组和链表(单向),在JDK1.8的时候参加了红黑树
数组的长度一定是2的n次方 即使带参数的构造也会将初始参数转换成2的n次方
数据存放的的时候,根据K的hash值判断存放在数组的哪一个位置,如果对应的这个位置有了,以链表的方式继续存放下去。当存的长度达到8的时候,链表转换成红黑树
存放的数据个数默认情况下达到数组的长度的0.75会促发扩容
key 和value都可以位null
方法
v put(key ,value) ----添加数据
当put添加的key值相等时, 那么后添加的会先把先添加 的覆盖
v remove (key)-----删除
v get(key)-------通过键获取值
int size()——键值映射的数量
void clean()——清空所有键值对
boolean contaninKey(key)——判断是否包含指定的key
boolean contain Value(Value)——判断是否包含指定的value
boolean isEmpty()——判断集合是否为空
v replace(key,value)——替换指定的key的value值
Set keySet()——将所有的key放入一个set集合中
遍历
//将所有的key放入一个set集合中 Set<String> keySet = map.keySet(); //增强for循环可以遍历set集合 for (String key : keySet) { System.out.println(key); String value = map.get(key); }
//遍历map Set<Entry<String, String>> entrySet = map.entrySet(); for (Entry<String, String> entry : entrySet) { System.out.println(entry.getKey() + entry.getValue()); }
HsahTable
也是实现了Map接口,所以单纯的从使用的角度来说,和HashMap时没有却别的
特点
无参构造 ,默认传了数组的初始长度位11,负载因子0.75
底层的数组结构为数组+链表(单向)
每次触发扩容为原本的数组长度的2倍+1
key和value都不能为空
线程是安全的
TreeMap
底层数据结构是红黑树,没有数组,所以没有初始值这个概念
构造主要传入的是比较器
要想实现排序有两种方式
1.java.util.Compartor 的对象传入构造
2.可以实现java.lang.Comparable接口
这两个方法都是返回int 小于0在左边,等于0不变,大于0在右边
比较器排序
让集合构造方法接收Comparator的实现类对象,重载了compare()方法
自然排序
重载了CompareTo()方法
collection
概述
是单列集合的顶层接口,它表示一组对象,这些对象也称为collecetion,
创建collcetion集合的对象
多态的方式
具体的实现类ArrayList
collection的集合遍历
Iterator
:迭代器,集合的专用遍历方式
子主题
Iteroter<E>iteroter():返回此集合中元素的迭代器,通过集合的iteraoter()方法得到。列如: Collection <String> c= new ArrayList<String>();//创建集合对象 Iteraotor<String> it= c.iterator();//通过c.iterater()返回了了 new Iter(实现类对象),
迭代器是通过集合的iterator()方法得到所以我们说它依赖于集合而存在
Iterator中常用的方法
E nex():返回迭代的下一个元素
bollean hasNext():如果迭代具有更多元素,则返回true
增强for循环
作用
简化数组和Collection,实现Iterator接口的类允许其对象成为增强型for语句的目标,期内部原理是一个迭代器
增强for格式
for(元素数据类型 变量名: 数组或者Collection){ // 在此使用变量即可,该变量就是元素 }
范例
int[ ] arr={1,2,3,4,5,}; for(int i:arr){ System.out.println(i); }
list集合
list集合特点
有序:储存和取出的元素顺序一致
可重复性:存储的元素可以重复
方法
Public boolean add(element)将指定的元素添加的集合末尾
public void add(int,element)。将集合中的指定位置添加指定元素
public boolean remove(object o):删除指定的元素,返回元素是否删除成功
public E remove (int index):删除指定索引处的元素,返回被删除的元素
public E set(int index, E element):修改指定索引处的元素,返回被修改的元素
public E get(int index):返回指定索引处的元素,
public int size ():返回集合中的元素个数
public void clear(); 从列表中删除所有元素。
public booolean contains(element ): 判断集合是否包含某一元素
public int indexof( element):从左往右去找指定元素,找到就返回对应索引,没有就返回-1
public int lastIndexof( element):从右往左去找指定元素,找到就返回对应索引,没有就返回-1
public boolean isEmpty():判断集合是否为空,如果是
List集和分类
ArrayLisr:
底层数据结构是数组,查询快,增删蛮,
非线程安全 ,每次扩容为原本的1.5倍
LinkList:
底层数据结构是链表,查询慢。增删快
线程安全
LinkedList集合的特有功能方法
piblic void addFirst(E e):在该列表开头插入指定的元素
public void addLast(E e):将指定的元素追加到此列表的末尾
public E getFirst():返回此列表中的第一个元素
public E getLast():返回此列表中的最后一个元素
piblic E renoveFirst():从此列表中删除并返回第一个元素
public E removtLast():从此列表中删除并并返回最后一个元素
Vector
和ArayList大至相同,如果没有指定扩容的值,则每次扩容为原来的2倍,效率相当于ArrList低一些
线程安全
使用无参构造的时候,会创建一个长度为10的素组,以后每次扩容为原本的两倍
使用带参构造的时候,可以指定初始数组的额长度,还可以指定扩容的长度
public Vector(int initiaCapacity , int capacityIncream) initialCapacity 初始数组的长度 capacityIncrement 扩容增长的长度 如果没有指定默认是0 那么扩容就为原本的两倍
Set集合
集合概述特点:1.不包含重复的元素2.没有带索引的方法,所以不能使用普通for循环遍历。3.无序的
元素的唯一性
子主题
哈希值
常见数据结构之哈希表
JDK8之前,底层采用数组+链表实现可以说是一个元素为链表的素组 JDK8之后,在长度比较长的时候,底层实现了优化
哈希值是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
Object类中有一个方法可以获取对象的哈希值 public int hashCode():返回对象的哈希值
对象的哈希特点
1.同一个对象多次调用hashCode()方法返回的哈希值是相同的 2.默认情况下,不同对象的哈希值是不同的,重写hashCode()方法可以实现让不同对象的哈希值相同
HashSet集合概述和特点
1.继承自HashMap的key
2.对集合的迭代顺序不作任何的保证,也就是说不保证存储和取出的元素顺序一致
3.没有带索引的方法,所以不能使用普通for循环遍历
4.由于是Set集合,所以是不包含重复元素的集合
程序向HashSet中添加一个对象时,先用hashCode方法计算出该对象的哈希码。比较: (1),如果该对象哈希码与集合已存在对象的哈希码不一致,则该对象没有与其他对象重复,添加到集合中!(2),如果存在于该对象相同的哈希码,那么通过equals方法判断两个哈希码相同的对象是否为同一对象(判断的标准是:属性是否相同) 1>,相同对象,不添加。 2>,不同对象,添加!
LinkedHashSet集合概述与特点
继承自hashSet集合
1.哈希表和链表实现的Set接口,具有可预测的迭代次序
2.由链表保证元素有序,也就是说元素的储存和取出顺序是一致的
3.由哈希表保证元素唯一,也就是说没有重复的元素
TreeSet集合概述和特点
继承自HashMap
元素有序:这里的顺序不是指储存和取出的顺序,而是按照一定的规则进行排序,具体的排序方法取决于构造方法
TreeSet(),根据其元素的自然排序进行排序
TreeSet(Comparator comparator):根据指定的比较器进行排序
没有带索引的方法,所以不能使用普通的for循环遍历
由于是Set集合,所以不包含重复元素的集合
ListIterator列表迭代器
通过List集合的listIterator()方法得到,所以说它是List集合特有的迭代器 用于允许程序言任意方向遍历列表的迭代器,在迭代期间修改列表,获取列表中迭代器的当前位置
ListIterator中常用的方法
E nex():返回迭代的下一个元素
bollean hasNext():如果迭代具有更多元素,则返回true
E previous():返回列表中的上一个元素
bollean hasPrevious(): 如果迭代器在相反方向遍历时,具有更多的元素,则返回true
子主题
浮动主题
并发修改异常--ConcurrentModifaction
原因
迭代器遍历的过程中,通过集合修改了集合中的元素造成了迭代器获取元素中判断预期修改值和实际修改值不一致