- 浏览: 110342 次
- 性别:
- 来自: 火星
文章分类
最新评论
-
angry-jerks:
xucaishen 写道我想问一下,怎么查找当前类的方法?就像 ...
Intellij IDEA使用总结 -
xucaishen:
我想问一下,怎么查找当前类的方法?就像eclipse里面的ct ...
Intellij IDEA使用总结 -
laugh2last:
不错,好好温习了一下,简单明了,
Intellij IDEA使用总结 -
Will.Du:
挺好,比较详细
Intellij IDEA使用总结 -
cowboy_bebop:
test comment
IntelliJ IDEA 优化.
从源码的高度来看看集合中各个实现类的是如何组织我们存进去的数据的,主要包括Java类库中提供的几个具体的类:
LinkedList
ArrayList
HashMap
HashSet
TreeMap
TreeSet
PriorityQueue(顺序按下面的讲解顺序)
-----------------------------------------------------------------------------------------------------
1、java.util.LinkedList<E>
当我们创建一个LinkedList类的对象,并且试图增加一个新的元素的时候,到底是如何组织我们传进去的数据的呢? //创建一个LinkedList类型的对象
java.util.LinkedList<String> l=new java.util.LinkedList<String>();
l.add(e);//e为E类的对象
打开add方法的源码看看: public boolean add(E e) {
//调用LinkedList的私有方法
//header是LinkedList中的一个属性,这样定义的private transient Entry<E> //header = new Entry<E>(null, null, null);
addBefore(e, header);
return true;
}
//被调用的私有方法
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
//Entry<E>是LinkedList的内部类,包装每一个E类型的对象e,形成一个链表
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;
}
}
我们惊喜的发现,原来就是把我们传去的e对象包装成了Entry<E>,然后通过Entry<E>的next和previous两个
属性形成了一个以包装后的e对象(即Entry<E>)为节点的双向链表。
于是我们彻底明白了LinkedList果然名副其实,就是一个链表嘛!
-----------------------------------------------------------------------------------------------------
2、java.util.ArrayList<E>
我们看看在ArrayList对象调用add();方法时,底层到底是如何执行的 public boolean add(E e) {
ensureCapacity(size + 1); // size是ArrayList中元素的个数
elementData[size++] = e; //在调整后的elementData末尾加入新的元素
return true;
}
public void ensureCapacity(int minCapacity) {
modCount++;
//elementData就是ArrayList中一个数组类型的属性,用来放进去的元素: //Object[] elementData
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {//原来的elementData空间不够用了!
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
//如果通过oldCapacity 计算出的新空间依然不够用
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
//这一步最后会调用System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//来实现将所有的元素copy到长度更大的数组中,这一步将很费时间
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
于是我们发现:原来ArrayList也是如名字说的,用Array组织数据。不过它内部定义的那个调整elementData数组的方法copy太多,
显然当数据量大的时候,性能不会很好。
-----------------------------------------------------------------------------------------------------
3、java.util.HashMap<K,V> //向HashMap中插入键值对
public V put(K key, V value) {
if (key == null) //如果没有输入的key是null值
return putForNullKey(value);//插在Entry[0]的第一个,返回null
//获得哈希码
//1、首先用key类定义的hashcode()方法计算得到一个int
//2、进行一些>>>和^的操作
int hash = hash(key.hashCode());
//通过&运算将hash按二进制位取反(1变为0,0变为1)
//得到要插入的元素在table中的index
int i = indexFor(hash, table.length);
//遍历table[i]数据元下拖带的一个链表的所有元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果有一个已经存在的元素的哈希码"=="为true,
//并且key值"=="或者"equals"为true
//也就是所谓的key经过hashcode()的一系列运算和
//equals()的一系列运算相同的元素,就替换原来的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//把原来在table[i]位置的元素挤到Entry<K,V>的next位置
addEntry(hash, key, value, i);
return null;
}
}
想必大家看这段代码都看到晕了吧,为了让大家能够更加形象的人知道HashMap对数据的的组织形式,上了一个HaspMap数据结构图:
这里解释一下,这个图的最左边的一些就是上面源码中的table也就是HashMap的一个属性Entry[] table。
将一个新的键值对插入需要经过这几步:
---给key值计算哈码(计算在这一步int hash = hash(key.hashCode());),
---得出在table数组的中index:int i = indexFor(hash, table.
length);
---将键值对插入index确定的上图所示的一个横向的链表中。如果在这个链表中有要插入的pair的key经过hashcode()的
一系列运算和equals()的一系列运算相同的元素,就替换原来的value。(这也就是我们自己定义的类要用到HashMap
存储的时候,必须重写hashcode()和equals()方法,并且要保证对同一对象两个方法计算结果要相同的原因。
因为如果不相同,在一个同一对象为key插入值的时候就不会像你期望的那样后插入的value覆盖前面的value了,
而是会重新开辟一个空间存储)
于是,到这里我们明白了,原来HashMap就是通过散列表这种数据结构组织数据的!
-----------------------------------------------------------------------------------------------------
4、java.util.HashSet<E> public boolean add(E e) {
//map是该类的一个属性,这样定义的:HashMap<E,Object> map
//这里e作为key了
//value用本类的属性代替private static final Object PRESENT = new Object();每个键值对都相同
return map.put(e, PRESENT)==null;
}
小样直接自己不解决,抛给HashMap类的put()方法,也就是用一个散列表存数据。详解见第三条对HashMap的讲解
-----------------------------------------------------------------------------------------------------
5、java.util.TreeMap<E> public V put(K key, V value) {
Entry<K,V> t = root;//root是整棵树的根节点
if (t == null) {
//插入的第一个元素会成为根节点
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 调用Comparator的compare()方法确定新加的元素出现的位置。
//我们可以再自己定义的类中实现Comparator接口,然后传给树集的构造器。从而按照自己定义的不同的比较规则来给
整个树的数据进行排序。
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//这里我们将传进来的数据包装成Entry<K,V> ,通过Entry<K,V> 内部类的//属性 Entry<K,V> parent来组织一棵树
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
我们又可以开心的大笑了,原来就是如此简单,就是按照一定的规律形成一棵二叉树来存数据。
大笑过后,我们再次静下心来观察,源码中出现了这样一句:k.compareTo(t.key);是说用key对应的类中实现
的compareTo()方法来判断两个key的先后顺序。有若干标准的java平台类都实现了Compatable接口(Compatator可
以自己定义不同的比较规则,不过这个接口的比较规则只有一个,是定义key的类的时候定义的,没有可变性),如String类: //用字典式排序。不展开分析了。
public int compareTo(String anotherString) {
int len1 = count;
int len2 = anotherString.count;
int n = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
if (i == j) {
int k = i;
int lim = n + i;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
} else {
while (n-- != 0) {
char c1 = v1[i++];
char c2 = v2[j++];
if (c1 != c2) {
return c1 - c2;
}
}
}
return len1 - len2;
}
所以,我们自己定义key的类的时候,要特别注意compareTo()方法中算法的选择,以便有一个最好的插入、查找、
遍历的性能。一般而言将元素添加到树集的速度快于数组和链表,慢于散列表(素服比较:数组、链表<树集<散列表)。
-----------------------------------------------------------------------------------------------------
6、java.util.TreeSet<E> public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
相信大家看到源码立马就能明白了吧,向HashSet一样TreeSet也偷懒了(至于为什么要偷懒,感兴趣的朋友可以去研究,
这里不展开了),也是用二叉树的结构存数据,不多说!
-----------------------------------------------------------------------------------------------------
7、java.util.PriorityQueue<E>
我们看看调用add()方法在底层到底发生了什么事情! public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
//前面这的几行无非就是判断非空,判断本类的属性queue的长度是否够用然后做相应调整
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
//最后终于要将元素插进去了
//如果queue空就插在index为0的位置,很好理解
//否则调用siftUp()方法(第一个参数是the position to fill,第二个参数是the element to insert)
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
//再来看看siftUp()方法是如何实现的
//api文档的注释的意思是:将x插入合适的位置保持heap的有序性不变
//排序标准有两种途径获取:
//1、在构造PriorityQueue的时候传入的Comparator ,这个优先选用
//2、 要插入的x自己实现的compareTo方法
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//这里我只需分析comparator的情况就可以了
private void siftUpUsingComparator(int k, E x) {
//最坏的情况是:我找了一圈发现x才是整棵树种最小的。这时k为0,也就是到达整个堆的最小的元素
(或者整棵树的根节点),停止循环。
while (k > 0) {
//第一句的意思是获得要插入的这个k位置在queue中对应的父元素的索引
//我可以告诉大家这个式子的计算结果是:queue[n]节点的子节点是queue[2*n+1]和queue[2*(n+1)]
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//如果比较规则确定x"大于"父节点,就插在k位置了,跳出循环
if (comparator.compare(x, (E) e) >= 0)
break;
//如果发现x较小,就将父节点的元素移到这个k位置
queue[k] = e;
k = parent;//现在要插入的位置变为原来父节点的位置
}
queue[k] = x;//
}
嗯,这个类用了一种“堆”(逻辑上是二叉树,存储上用数组,树中的元素有大小关系,越小在数组中的index也越小)
的数据结构。
典型应用是存储有优先级的任务,因为每次调用remove移除最小的元素(优先级最高的元素),都会自动排序,
保证每次移除的都是优先级最高的任务。 同样,TreeMap逻辑上也是通过有序二叉树来组织数据的,不过,TreeMap通过节点的链接来组织存储结构, 而PriorityQueue是通过数组的一些列计算确定逻辑上的树的节点的存放位置。
发表评论
-
模拟spring @Resource方式的依赖注入.
2011-10-24 22:12 1464package org.cgz.test; ... -
Java内存泄露(摘录)
2011-04-27 10:08 4561问题的提出 Java的一个重要优点就是通过垃圾收集器(G ... -
Hash 存储机制
2011-03-14 12:59 1172HashMap 和 HashSet 是 Java C ... -
字符串的一些问题
2011-02-06 16:37 884A: String str1 = "java&quo ... -
使用Map来实现频率统计
2010-11-13 00:48 1308import java.util.HashMap; i ... -
获取图片的高度和宽度
2010-11-12 12:15 1076java.io.File file = new java.io ... -
Java对编码问题的总结
2010-11-09 11:15 865总结下这两天对编码的认识一些认识,本文显得比较啰嗦,应为这 ... -
java 异常
2010-11-03 11:59 914本文从Java异常最基 ... -
java代码性能优化
2010-10-28 10:02 1888一、避免在循环条件中使用复杂表达式 ... -
ClassLoad分析
2010-10-27 15:09 20391 前言 ClassLoader 是 ... -
一个Java字符串过滤函数的性能优化
2010-10-19 21:19 1570一、需求 给定一个String对象,过滤掉除数字 ...
相关推荐
Java基础知识:数据类型、关键字、面向对象、集合框架、异常处理等 Java核心技术:I/O、多线程、网络编程、反射、泛型等 Java虚拟机:内存模型、垃圾收集器、类加载机制等 Java企业级开发:Spring、Hibernate、MyBatis等...
零、:rocket::rocket::rocket:数据结构与算法 一、:high-speed_train::railway_car::railway_car::railway_car:集合框架源码分析 集合框架 (第 13 篇) 源码分析:LinkedHashMap 集合框架 (第 14 篇) 源码分析:...
SSM框架的模块化设计使得系统结构清晰、易于维护,同时提供了强大的数据处理能力,满足了养殖业信息管理对大数据量、高并发性的需求。Java语言的面向对象特性和丰富的库函数则为系统的开发提供了有力保障,实现了...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
内容涵盖绝大部分Android程序员需要的技能:「数据结构算法」「程序架构」「设计模式」「性能优化」「组件化」「插件化」「热修复」「 NDK技术」「自定义检视」「性能优化」「 Android原始分析」「深入理解Kotlin 」...
集合框架 深入浅出JVM JVM内存模型 性能调优、线上问题排查 类加载机制详解 垃圾回收机制 垃圾回收器、垃圾回收算法 并发与多线程 线程状态转换与通信机制 线程同步与互斥 线程池知识点 常见的JUC工具类 常用工具集 ...
数据结构 Linux运维 P8架构 面试题汇总 目录 :面向对象,集合,IO流等 :HashMap,ConcurrentHashMap扩容原理等 :线程状态,ThreadLocal,强软弱虚引用,自定义线程池 :类加载过程,双亲委派机制 :syncro
深入理解系列(多看点源码,看看人家的设计) [go深入理解context] [go深入理解channel,锁] [go相对路径示例] [goruntime详解] go leetcode sql 性能优化 leetcode go 数据结构与算法之美 基础篇 go k8s实战 go MySQL...
包含了多个模块的面试题讲解,如:Redis、MySQL、框架、微服务、消息中间件、数据结构、Java集合源码分析、多线程、JVM、设计模式、高并发场景、企业实际问题场景等等各个方面逐一讲解。 欢迎在观看同时参考这篇博客...
│ 大型公司面试必答之数据结构与算法(一)-达摩老师.mp4 │ 大型公司面试必答之数据结构与算法(二).mp4 │ ├─面试必问-JVM性能调优 │ JVM性能调优 2018-10-25.mp4 │ ├─面试必问-mybaits源码分析 │ │ ...
7.2.1、WEB开发的标准目录结构 7.2.2、使用JSP的page指令导入所需要的JavaBean 7.2.3、使用指令 7.3、JavaBean与表单 7.4、设置属性: 7.4.1、设置指定的属性 7.4.2、指定设置属性的参数 7.4.3、为属性设置...
论文不仅展示了SSM框架在构建高效、稳定、可扩展Web应用方面的强大能力,还通过实际案例,让读者对SSM框架有了更为直观和深入的了解。 在实践上,本资源包提供了完整的源代码,包括前端页面、后端逻辑处理、数据库...
具备扎实的Java基础,熟练掌握集合,AQS,Synchronized关键字,CountDownLatch&Semaphore应用与原理,Executor线程池原理与源码,深入理解同步器AQS阻塞队列BlockingQueue,Future&ForkJoin框架原理,无锁并发框架...
7.2.1、WEB开发的标准目录结构 7.2.2、使用JSP的page指令导入所需要的JavaBean 7.2.3、使用指令 7.3、JavaBean与表单 7.4、设置属性: 7.4.1、设置指定的属性 7.4.2、指定设置属性的参数 7.4.3、为属性设置...
7.2.1、WEB开发的标准目录结构 7.2.2、使用JSP的page指令导入所需要的JavaBean 7.2.3、使用指令 7.3、JavaBean与表单 7.4、设置属性: 7.4.1、设置指定的属性 7.4.2、指定设置属性的参数 7.4.3、为属性设置...
7.2.1、WEB开发的标准目录结构 7.2.2、使用JSP的page指令导入所需要的JavaBean 7.2.3、使用指令 7.3、JavaBean与表单 7.4、设置属性: 7.4.1、设置指定的属性 7.4.2、指定设置属性的参数 7.4.3、为属性设置...
与DotNet数据对象结合的自定义数据对象设计 (二) 数据集合与DataTable 与DotNet数据对象结合的自定义数据对象设计 (一) 数据对象与DataRow ASP.NET中大结果集的分页[翻译] .net 2.0 访问Oracle --与Sql Server的...
不但详细介绍了Java语言本身,而且讨论了面向对象的设计思想和编程方法、UML建模语言、图形用户界面的编程方法、网络和数据库程序的编程方法、线程的使用、Java集合框架等实用开发技术。全书以面向对象的程序设计...
最新Python3.5零基础+高级+完整项目(28周全)培训视频学习资料;本资料仅用于学习。 【课程内容】 第1周 开课介绍 python发展介绍 第一个python程序 变量 字符编码与二进制 字符编码的区别与介绍 ...数据结构其他