- 浏览: 88006 次
- 性别:
- 来自: 北京
最新评论
-
hpu423:
...
JAVA 字符串常量池 -
hpu423:
[c[flash=200,200][flash=200,200 ...
JAVA 字符串常量池 -
liubang201010:
Foglight 监控OC4j自2004年左右, Oracle ...
OC4J 10.0.3 安装 配置 详解
读JDK源码-集合部分
- 博客分类:
- J2SE
以前读过一遍JDK源码的集合部分,读完了一段时间后忘了,直到有一次面试简历上还写着读过JDK集合部分的源码,但面试官让我说说,感觉记得不是很清楚了,回答的也模模糊糊的,哎,老了记性越来越差了,所以再回头来读一遍,并且在这里做个笔记,省的又忘了,java.util里的集合类的源代码本身不是很难,就一个一个的记录吧:
(1).ArrayList:
此类底层数据结构是数组:
另外还有一个属性是用来记录size的,感觉JDK源码实现的确实很优雅,他里面的属性不多也不少,都用到很精妙。
三个构造函数:
添加一个元素:
添加一个集合进来:
remove(int index),get和set方法都是直接对数组指定位置的元素进行操作。
remove(Object obj),indexOf(Object obj)方法这样一些方法都是对数组的遍历,ArrayList中运行存放null,ArrayList是比较简单的。
(2).HashMap:
HashMap就是用hash方式映射key-value,底层实现是数组+链表的方式,通过hash码定位索引,如果有重复的索引存在就以链表的方式存放索引相同的元素,HashMap中会预分配空间,初始默认分配16个空间存放元素。
以数组+链表的方式存放元素:
Map中的Entry就不在此列出了。。。
再看看他的变态的hash方法,我也没看明白,就先放这把,哪位要是看懂了给我回复一下:
接下来我们就来看看HashMap是怎么样进行增删改查的
增加元素:
移除一个元素,因为这里涉及到数组和链表两种数据结构,所以移除时要分清楚:
查找就不多说了,看代码也比较简单。
(3).HashSet
看完了HashMap再看HashSet比较简单了,因为HashSet底层是HashMap实现的,要添加的元素作为HashMap的key,private static final Object PRESENT = new Object();作为value,由此可见HashSet是不允许有重复元素的。
(4).LinkedList
现在该LinkedList出场了,这个是我们数据结构里所学的双向链表,如果数据结构双向链表学到不错的话这个里面的代码也挺好理解的,首先看看他的field和constructor:
以下几个增删查到方法都比较简单。
【补充】迭代器:待续
(1).ArrayList:
此类底层数据结构是数组:
private transient Object[] elementData;
另外还有一个属性是用来记录size的,感觉JDK源码实现的确实很优雅,他里面的属性不多也不少,都用到很精妙。
三个构造函数:
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } public ArrayList() { //[b]由这个无参构造可以看得出默认分配的capacity是10个[/b] this(10); } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
添加一个元素:
//默认添加到数组最末尾 public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //ensureCapacity方法确认一下数组长度,当长度不够minCapacity时就重新分配数组空间,在add方法中调用了此方法,传递给形参minCapacity的值为size+1、即有当前一个元素的空间就可以了,由此可以看出ArrayList的空间不是预先加载的,int newCapacity = (oldCapacity * 3)/2 + 1就表示新添加到空间的大小是原来长度的一半。 public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; [b] int newCapacity = (oldCapacity * 3)/2 + 1[/b]; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } //此方法是在指定位置添加一个元素,将此位置后的元素向后移动一个空间。 public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
添加一个集合进来:
//追加一个集合到list中,先确认了数组空间是否能容纳的下要添加到元素,然后利用了System.arraycopy方法将所有元素复制进数组中,实现起来很容易。 public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacity(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + size); Object[] a = c.toArray(); int numNew = a.length; ensureCapacity(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }
remove(int index),get和set方法都是直接对数组指定位置的元素进行操作。
remove(Object obj),indexOf(Object obj)方法这样一些方法都是对数组的遍历,ArrayList中运行存放null,ArrayList是比较简单的。
(2).HashMap:
HashMap就是用hash方式映射key-value,底层实现是数组+链表的方式,通过hash码定位索引,如果有重复的索引存在就以链表的方式存放索引相同的元素,HashMap中会预分配空间,初始默认分配16个空间存放元素。
以数组+链表的方式存放元素:
transient Entry[] table; Entry是一个静态内部类,他实现的是[b]Map接口中的一个内部接口[/b],接口也可以有嵌套定义的,长见识了。: static final int DEFAULT_INITIAL_CAPACITY = 16;//默认的初始分配空间大小 static final int MAXIMUM_CAPACITY = 1 << 30; //最大能分配的空间,写JDK的人真能装的,好端端的写个常数就行了,1左移一次相当于乘2,那就是2^30=1073741824(我也是计算器算的) static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子。 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; //典型的单向列表,后面的LinkedList还用到了双向列表。 final int hash; ....... }
Map中的Entry就不在此列出了。。。
再看看他的变态的hash方法,我也没看明白,就先放这把,哪位要是看懂了给我回复一下:
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
接下来我们就来看看HashMap是怎么样进行增删改查的
增加元素:
//可以添加<null,null>进去哎 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; } //根据hash值计算索引位置的 static int indexFor(int h, int length) { return h & (length-1); } //添加到元素不存在,在链表头添加元素 void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } //既然看到resize方法就说一下吧 在addEntry方法里看到一个threshold的属性,该属性的值为capacity * loadFactor,当当前元素的个数超过threshold时就扩展数组大小,包括链表上面的元素。 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
移除一个元素,因为这里涉及到数组和链表两种数据结构,所以移除时要分清楚:
final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //prev和e都初始为链表第一个元素 while (e != null) { //检查链表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) //移除的就是链表第一个元素 table[i] = next; else //要移除的就是e,将prev的next指向e的next。 prev.next = next; e.recordRemoval(this);//看了一下这个方法里没有代码。 return e; //移除后的元素就交给GC了。 } prev = e; e = next; } return e; }
查找就不多说了,看代码也比较简单。
(3).HashSet
看完了HashMap再看HashSet比较简单了,因为HashSet底层是HashMap实现的,要添加的元素作为HashMap的key,private static final Object PRESENT = new Object();作为value,由此可见HashSet是不允许有重复元素的。
public boolean add(E e) { return map.put(e, PRESENT)==null; //put方法返回与key关联的旧值,如果没有旧值就返回null,而在HashSet中PRESENT是个常量,所以第一次add时返回true,以后add时返回false,表示重复添加了,但实际上也添加进去了,只是key都一样,value都是PRESENT. } public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); } public Iterator<E> iterator() { return map.keySet().iterator(); }
(4).LinkedList
现在该LinkedList出场了,这个是我们数据结构里所学的双向链表,如果数据结构双向链表学到不错的话这个里面的代码也挺好理解的,首先看看他的field和constructor:
private transient Entry<E> header = new Entry<E>(null, null, null); public LinkedList() { header.next = header.previous = header; //一开始表头元素的前驱和后继都指向了自己 } //静态内部类 private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
以下几个增删查到方法都比较简单。
public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; } public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; } public E removeFirst() { return remove(header.next); } public E removeLast() { return remove(header.previous); } public void addFirst(E e) { addBefore(e, header.next); } public void addLast(E e) { addBefore(e, header); } public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }
// 更新: public E set(int index, E element) { Entry<E> e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { //entry方法在此处采用了二分法查找 for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
【补充】迭代器:待续
发表评论
-
JDK Tools and Utilities
2013-04-11 14:32 1234Oracle官方网址:http://docs.oracle.c ... -
【转载】深入理解Java虚拟机》笔记
2013-04-10 09:59 984【转自】http://www.admin10000.com/d ... -
Sun java命令的JVM参数收集【持续更新】
2013-04-10 09:33 2929从网络上看了很多的关 ... -
【转载】Java的内存回收机制
2013-04-10 08:52 912【转自】 http://www.admin10 ... -
JDK动态代理深究
2013-03-28 15:22 1393JDK的动态代理涉及到了JAVA的动态编程,说起来也惭愧,我写 ... -
JAVA 字符串常量池
2012-05-15 10:59 48281. 首先String不属于8种基本数据类型,String是一 ... -
java String类的split方法
2012-04-18 17:24 1558String str = "==he=llo==& ...
相关推荐
JDK源码【1.7/1.8/1.9】,方便查看代码; Java官方demo。 JDK源码【1.9】,模块化系统、JShell、集合工厂方法等
集合源码 JDK-Collection集合入门 总的list和set类结构大致如下所示 Map不继承Collection,其结构如下 首先介绍下迭代器的概念 迭代器无非是一个接口,假设我们有一个数组,如果我们要实现迭代器,只需要根据该接口定义...
jdk1.8源码(包含1.8API),想提升JAVA技术,阅读JDK源码必不可少,里面的IO框架,集合框架,并发框架等经典源码都值得一读!
源码解析jdk8.0集合:HashMap的底层实现原理.pdf
源码解析jdk7.0集合:HashSet的底层实现原理.pdf
Java通用 Java基础用法,集合,线程,JUC,jdk5--8各个版本特性。代码示例和源码分析每个包的package-info.java有详细的说明和参考资料
源码解析jdk7.0集合:ArrayList的底层实现原理.pdf
java 类源码 JavaCollection 基于JDK1.8的集合类源码分析
java 集合源码学习
学Java的最佳途径之一就是坚持阅读它的源码,不是JRE的源码,那些你读了也吸收不了多少,而是常用类库的源码,就是我们常用的那些类,尤其是集合类。源码里蕴含着丰富的代码技巧,设计模式,编程风格,绝对是大师级...
源码解析jdk7.0集合:LinkedList的底层实现原理.pdf
计算机后端-Java-Java核心基础-第25章 集合02 12. HashMap在JDK8中的源码分析.avi
计算机后端-Java-Java核心基础-第25章 集合02 11. HashMap在JDK7中的源码分析.avi
摘自jr源码,是jdk的源码,有需要研究java集合类的可以下载
源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf
因为JDK源码的命名过于简略, 不容易被理解, 但是通过我所实现的这些集合就能知道JDK中大概是怎么实现的了, 如果笔记做得有错误, 大家可以给我提issuses =,= 注意点一 本仓库为Java集合类进行源代码的分析笔记, 同时...
java8集合源码定时器和定时器任务 定时器是线程调度任务以在后台线程中执行的工具。 任务可以安排为一次性执行,或定期重复执行。 与每个 Timer 对象相对应的是一个单独的后台线程,用于按顺序执行所有计时器的任务...
java8集合源码核心-Java java中堆和栈的区别? Java 8 发布的重要特性是什么? 什么是 JVM,它是否独立于平台? 什么是 JIT 编译器? Java中的类加载器是什么? 什么是不同类型的类加载器? Java Compiler 存储在 ...
本仓库记录了我的Java学习进阶之路,涵盖了Java基础、JDK源码、JVM中的重要知识,附有代码和博客讲解,旨在提供一个Java在线共享学习平台,帮助更多的Java学习入门者进阶。 Java学习 本仓库记录了我的Java学习进阶...
shuffle源码Databricks - Apache Spark:trade_mark: - 2X 认证开发人员 这个 repo 是我的认证准备笔记的集合。 如果您有任何建议,找到更正或想要欣赏,请发表评论:-) 关注我,,,, 指数 1. 一般影响链接 用于快速...