总结概括终结篇,疯狂Java笔记之常见java集合的实现细节
HashSet和HashMap的关系

HashSet和HashMap有很多的相似之处,对于HashSet而言,采用了Hash算法来决定元素的存储位置,HashMap而言,将value当成了key的附属品,根据Key的Hash值来决定存放的位置。

有一点需要说明一下,经常听说,集合存储的是对象,
这其实是不准确的。准确来说,集合中存储的其实是对象的引用地址或者称为引用变量。而引用地址或者引用变量指向了实际的java对象。java集合实际是引用变量的集合而非java对象的集合。

通过之前的源码解析其实可以发现,HashMap在存放key-value时,并没有过多的考虑value的内容。只是根据key来确定key-value对在数组中应该存放的位置。HashMap的底层是一个Entry[]数组,key-value组成了一个entry。当需要向HashMap中添加元素时,首先根据key的hashcode来确定在数组中存放的位置,如果key为null,采用特殊方法进行处理,存放在数组的0号位置。如果当前位置已经有元素存在,则遍历单链表,如果两个key相等,则用新值替换掉旧值,如果key不相等,则插入到链表中。有一点需要说明,在jdk8之前,hashmap使用数组+单链表存储,在8后,采用了数组+链表+红黑树存储。

对于HashSet要说的没有太多,HashSet的实现也是比较的简单,它的底层使用HashMap实现的,只是封装了一个HashMap对象来存储所有的集合对象。

Iterator迭代器

fast-fail快速失败机制

在迭代的过程中,如果删除了某一个元素,collection会抛出ConcurrentModificationException异常。

为什么会出现这个异常呢?这是因为在迭代时,某个线程对该collection在结构上进行了更改,从而产生fail-fast.当方法检测到对象修改后,但是不允许这种修改就会抛出该异常。fail-fast只是一种异常检测机制,JDK并不能保证该机制一定会发生。

通过一个demo来详细的说明下:

LinkedList<String> list = new LinkedList<String>();list.add;list.add;list.add;list.add;for (String a : list) { System.out.println; list.remove;}

执行上面的代码便会抛出
java.util.ConcurrentModificationException;来看一下LinkedList
remove()方法的源码:

 //删除方法 public E remove(int index) { checkElementIndex; //验证index是否合法 return unlink(node; //调用unlink方法 } E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; //modCount+1 敲黑板划重点 return element; }

关于上面代码的具体含义请自行查阅上面的文章。
上面代码在删除指定位置的元素后将执行私有内部类ListItr中的next()方法,进行下一个元素的遍历.

//在私有内部类ListItr中有如下的属性定义,再进行遍历时,将遍历对象的modCount值赋值给了expectedModCount。private int expectedModCount = modCount;public E next() { checkForComodification(); if (!hasNext throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item;}final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

运行next()方法后,会先执行checkForComodification()方法,判断modCount与expectedModCount是否相等,不相等则抛出异常。

因为是遍历对象单方面改变的modCount值,ListItr并没有监测到,所以变造成了modCount和expectedModCount不相等的情况。于是出现了异常。我的理解是,在使用迭代器进行对象遍历时,创建了一个新的引用,而新引用指向了遍历的对象,同时将遍历对象的一些属性赋值给了迭代器对象。调用遍历对象的方法时,对象的属性发生变化,而迭代器对象中的遍历对象的拷贝唯有进行更新,导致了值得不匹配,从而抛出异常。这只是我的个人理解,欢迎深入交流。

采用下面的方法就不会出现该异常,是因为迭代器对象进行了属性的更新!
通过Iterator的方法删除后,保证了modCount与expectedModCount值的统一。

Iterator<String> iterator = list.iterator(); while(iterator.hasNext{ String str = iterator.next(); if(str.equals{ iterator.remove(); } }

少年听雨歌楼上,红烛昏罗帐。 壮年听雨客舟中,江阔云低,断雁叫西风。感谢支持! ---起个名忒难

1.Iterator实现类与迭代器模式

Java的lteratar和Enumeration两个接口都是迭代器模式的代表之作,它们就是迭代器模式里的“迭代器接口”。所谓迭代器模式指的是,系统为遍历多种数据列表、集合,容器提供一个标准的“迭代器接口”,这些数据列表、集合、容器就可面向相同的“迭代器接口”编程,通过相同的迭代器接口访问不同数据列表‘集合、容器里的数据.不同的数据列表、集合、容器如何实现这个“迭代器接口”,
则交给各数据列表、集合、容器自己完成。

TreeSet和TreeMap的关系

TreeSet底层采用了一个NavigableMap来保存TreeSet集合的元素,但实际上NavigableMap只是一个借口,因为底层依然是使用TreeMap来包含Set集合中的元素。
与HashSet类似,TreeSet也是调用TreeMap的方法来实现一些操作。TreeMap的底层是使用“红黑树”的排序二叉树来保存Map中的每个Entry.关于TreeMap的实现在上面的链接中有详细的解释,请自行查阅。

HashSet和HashMap是无序的,而TreeSet和TreeMap是有序的

ArrayList和LinkedList

下面对上面的文章做一下总结,一些在上面文章中没有涉及到的点,在详细的说明一下。

1.Map的values()方法

不管是HashIvlap,还是TreeMap,它们的values()方法都可返回其所有value组成的Collection集合。按照通常理解,这个Collection集合应该是一个List集合,因为Map的多个valu。允许重复。
但实际上,HashMap,TreeMap的values()方法的实现要更巧妙。这两个Mad对象的values()方法返回的是一个不存储元素的Collection集合,当程序遍历Collection集合时,实际上就是遍历Map对象的value

HashMap和TreeMap的values()方法并未把Map中的value重新组合成一个包含元素的集合对象,这样就可以降低系统内存开销。

文章写到这,感觉该做一个总结了,也是时候结束了,
最常用的集合类基本上已经写完了,剩下的就不再继续探索了,感兴趣的自行研究,应该还会有几篇番外篇,关于并发包JUC中的集合,如currenthashmap等类的探索,
不过要过段时间了。

2.HashMap和HashSet

在HashSet里,系统采用Hash算法决定集合元素的存储位置,这样可以保证快速存,取集合元素;对于HashMap而言,系统将value当初key的‘附属物’,系统根据Hash算法开决定key的存储位置,这个可以保证快速存,取集合key,而value总是紧随key存储。

集合号称存储的是Java对象,但实际上并不会真正将Java对象放入Set集合中,而只是在Set集合中保留这些对象的引用而己。也就是说,Java集合实际上是多个引用变量所组成的集合,这些引用变量指向实际的Java对象。对于java集合他只是多个引用变量的集合。

当程序试图将一个key-value对放入HashMap中时,首先根据该key的hashCade()返回值决定该Entry的存储位置—如果两个Entry的key的hashCade返回值相同,那么它们的存储位置相同:如果这两个Entry的key通过equals比较返回true,则新添加Entry的value将覆盖集合中原有Entry的value,但key不会覆盖;如果这两个Entry的key通过equal比较返回false
,则新添加的Entry将与集合中原有的Entry形成Entry链,而且新添加的Entry位于Entry链的头部

当系统开始初始化HashMap时,系统会创建一个长度为capacity的Entry数组。这个数组可以存储元素的位置被称为“桶(bucket)”,每个bucket都有其指定的索引,系统可以根据其索引快速访问该bucket里存储的元素。

无论何时,HashMap的每一个“桶”只存储一个元素(即一个Entry).由于Entry对象可以包含一个引用变量(就是Entry构造器的最后一个参数)用于指向下一个Entry,因此可能出现:HashMap的bucket中只有一个Entry,但这个Entry指向另一个Entry这就形成一个Entry链,如图:

图片 1

set.PNG

HashMap在每一个bucket里只有一个Entry,所以可以根据索引快速取出该bucket里的Enrty.当发生hash冲突时,单个bucket里存储的不是一个Entry,而是一个Entry链,系统会按顺序遍历每个Entry,知道找到想搜到的Entry为止,即使要搜索的末端,系统也会循环到最后找到该元素。

Java集合 —总体框架及主要接口,抽象类分析Java集合 —
ArrayList底层实现和原理Java集合 — Vector底层实现和原理Java集合 —
LinkedList底层实现和原理Java集合 — HashMap底层实现和原理Java集合 —
TreeMap底层实现和原理Java集合 — HashSet底层实现和原理Java集合 —
TreeSet底层实现和原理Java集合 — LinkedHashMap底层实现

3.ArrayList和LinkedList的性能分析和适用场景

当程序需要以get(int
index)获取List集合指定的索引出的元素,ArrayList性能大大的优于LinkedList。因为ArrayList底层以数组来保存集合元素,所以调用get(int
index)方法获取指定索引处的元素时,底层实际调用elementData[index]来返回改元素,因此性能非常好,而LinkedList则必须逐个的搜索。

当程序调用add(int index,Object
obj)向List添加数据是,ArrayList需要“整体搬家”才能实现添加,而LinkedList需要找到索引而不用整体搬家,当时找索引也需要消耗一些系统性能,因为他是逐个搜索。同理,删除也是这样子。

当添加的数据个数大于底层数组的长度时,那么ArrayList必须创建一个长度为原来长度1.5倍的数组,再由垃圾回收机制进行回收。这样系统开销也有点大了。而LinkedList就不存在这个问题。

不过从大多数应用场景来说ArrayList总体性能还是优于LinkedList。

Set和Map的关系

Set代表一种无序不可重复的集合,Map代表一种由多个Key-Value对组成的集合。表面上看它们之间似乎没有啥关系,但是Map可以看成是Set的扩展。为什么这么说呢?看下面的这个例子:

在Map的方法中有一个这样的方法,Set<k> keySet()
,也就是说Map中的键可以转化成一个Set集合。如果把value看成key的一个附属品,或者把key-value看成是一个整体,那么Map集合就变成了一个Set集合。

2.迭代是删除指定元素

对于TreeSet,
HashSet等Set集合而言,当使用Iterator遍历它们时,如果正在遍历最后一个集合元素,那么使用Set集合的remove()方法删除集合的任意元素并不会引发ConcurrentModificatianException异常,当正在遍历其他元素时删除集合的任意元素都将引发该异常。

网站地图xml地图