- 浏览: 309272 次
- 性别:
- 来自: 广州
博客专栏
-
多线程深入浅出
浏览量:48619
文章分类
最新评论
-
buffon918:
撸主1024
DB2 SQLSTATE 及其含义 -
学海无涯_小波:
我也在考驾照 累死了,不错 来几篇线程池的
Java线程及线程池专题 -
operthing:
operthing 写道
多线程——同步(synchronized)下 -
operthing:
...
多线程——同步(synchronized)下 -
ciding:
Jacarri_Chan 写道你觉得hibernate的优势和 ...
Hibernate-01-持久层发展过程
Java集合框架——HashMap与Hashtable
先来看看两个类的重点方法,再来比较。(这是我看源代码的思路,你也先去看看吧)
集合最主要的操作:写入,读取,移除。
/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * 接合指定的value与指定的key在这个map中,假如以前在这个map中包含这个key,以前 * 对应的value将会被替换 * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ 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; }
读源代码时,记得把上面的注释读一下,这是最快的理解方法的方式,不要一看源代码,就想着那几个for。
里面有几个关键点:
1:int hash = hash(key.hashCode());
2:int i = indexFor(hash, table.length);
3:addEntry(hash, key, value, i);
先说第1点:
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ 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的哈唏值的算法:(正好之前看过一篇博文,给出分析图,论坛地址是:http://www.iteye.com/topic/709945)
画的很好,所以就引用一下啊,至于分析的话,还是看原地址中的吧。(我说过,让你与我一起来这个过程,所以自己去看)。
第2点:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
这么少?那分析什么啊。这里真看不出来有什么好分析的,可是我运气比较好,看过一篇博文。这个地址忘记了,我就把内容写一下吧。
这里的关键点在于length的长度。
它是Entry[] table的长度,这个与HashMap的初始化时指定的。
先看一下HashMap的三个构造函数:
HashMap(int initialCapacity, float loadFactor)
HashMap(int initialCapacity)
HashMap()
从最后一个说起:
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
其中:DEFAULT_LOAD_FACTOR=0.75;DEFAULT_INITIAL_CAPACITY=16;
这是默认值,平时用的是不是这个呢?(今天看了之后,以后可以不用这个了,因为你要知道它的用意。)
第二个就不说了,直接第一个构造函数吧。(记得看一下注释)
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果你给出的容量大小大于HashMap支持的最大值时,取最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //下面的是关键:获取大于或等于的initialCapacity值的最小的2的n次方。 // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
看到了吧,这里有个2的n次方。回到先前说的indexFor方法
h&(length-1),这下知道道理了吧,保证在数组之内循环。(只能设计者太邪恶了,因为你只有把代码全部看懂才知道这个用处,好在分享者众多。)
再回到上面说的第3重点:addEntry(hash, key, value, i);
/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ 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); }
这里真没什么好说的,为了分析与Hashtable的不同,看看这个resize(2 * table.length);再到这个方法中的transfer(newTable);(其实这个在Hashtable与这没什么不同,引大家来是想学一下人家的设计思想,都是两个循环,因为HashMap可以有key为null的值,所以设计的时候,就得考虑进去。至于效率方面,两个没什么差别,但是可以看出在扩大容量时,是一个很耗时的工作。认清这点,虽然比较Hashtable没什么用,但是你在理解HashMap有用,与别的集合比较也有用,难道不是吗?)
/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
到此put方法就结束了。(看客还有什么好的要说的,就回复吧,因为我分享的同时,也希望能再深入点。)
第二大重点,读取
/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
代码本身没什么好说的,这里来看看构造函数对它的影响。
如果每个key的hash值都是不一样的,那就很快;反之,如果多个key的hash值一样,而table的深度就更深,获取的速度就有可能遍历到最后。
如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待。
再看移除:remove(Object key),与Hashtable没有什么区别的。
都是要遍历一次。并找到对应的key-value,将其移除。所以要它的时间复杂度o(n)。(等之后看了别的集合再说说。)
说完了。到Hashtable了。
构造函数差不多,不说。
不同点:
1,默认值不一样。0.75是一样的,initialCapacity为11。而且没有最大值,最小值是1。与2的30次方=1073741824
为什么没有最大值呢???(等写完这博文再去看看,这是突然想到的。)
2,hash的算法:直接用的int hash = key.hashCode();
而int index = (hash & 0x7FFFFFFF) % tab.length;与HashMap区别不大,因为HashMap支持key为null,而且固定的把第0位给了它,所以通过h&(length-1)把0给去掉。而这里的这个就是直接循环,对于null的支持,总是要点代价的。
3,就是刚说的对null的支持不同,Hashtable是不支持的。如果从源代码中,可以看到
if (value == null) {
throw new NullPointerException();
}
不支持value为null,而通过
int hash = key.hashCode();可以知道不支持key不能为null。
而HashMap支持有一个key为null,而value为null的不限制。
4,就是看看Hashtable在操作方法前都是有个关键字synchronized,不懂的去看我的博客,地址:http://ciding.iteye.com/blog/1300110 (Java多线程及线程池专题)
5,这个不是重点,也顺带说一下,Hashtable有一个contains(Object value)方法与containsValue(Object value)方法一样。而HashMap只有containsValue(Object value)方法。说这一点的原因是,在有的博文中乱写
只是将两个方法合并而已,引起误解也是因为没有看源代码。
先这到了。。。
评论
提供的是同步。
而HashMap也可以利用Collections类的静态的synchronizedMap()方法实现同步
这个同步的,其实还没有分析完。
在早期的jdk的设计中的同步,都是有缺点的,它用的synchronized关键字,在同步方法时,锁定了类对象。
在后期的版本中,同步都是通过lock来实现的,通过同步块实现,ConcurrentHashMap等类就是例子。
所以,像早期的Hashtable与Vector,Stack等都是一些过时的集合类。
本文没有提及这方面,这方面的内容打算放到总结来说明。
另外一点,有点要“破相”,对于集合的全局观还在建立中,真的是手上无招,心里没底。
因为感觉写的还不够好。
思路没有铺的很清楚,分析的不够具体。
只是踩一下,没说出我的弱点,没有收获的感觉很~~~~~~~~```
HashMap与Hashtable的遍历。
Map ma = new HashMap();或Map ma = new Hashtable();
Iterator iter = ma.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println("entry.getValue()="+entry.getValue());
System.out.println("entry.getKey()="+entry.getKey());
}
上面的方法是比较推荐的,还有一种很郁闷的方法:
Iterator iterator = hm.keySet().iterator();
while(iterator.hasNext()) {
System.out.println(hm.get(iterator.next()));
}
这方法很不好,点解?(广州话)
在while遍历一次,在hm.get(iterator.next()));的时候遍历一次
而最上面的。在while遍历后,就获取了。效率你懂的。
但是在这个地址:http://zhidao.baidu.com/question/332769610.html中人家说的话,你上去开骂也没机会。
提供的是同步。
而HashMap也可以利用Collections类的静态的synchronizedMap()方法实现同步
发表评论
-
mina框架 出现BufferUnderflowException异常的解决办法
2012-04-18 16:03 9106背景:使用mina进行socket编程,而传输数据大小会出现比 ... -
基于HttpClient 4模拟登录论坛
2012-04-08 23:19 12082package server; import java. ... -
Java集合框架——ArrayList与LinkedList
2011-12-29 11:16 0Java集合框架——ArrayList与LinkedList ... -
Java集合框架——基础接口
2011-12-21 12:23 5068Java集合框架专题(学习的那个过程,请指教) ... -
Java集合框架专题(学习的那个过程,请指教)
2011-12-19 15:02 2289Java集合框架专题 在这里提醒一下自己深入的思路,如 ... -
从JVM类加载的角度分析new String("")问题
2011-12-16 17:09 6008回来写博客了,还好,没有失言。 先告诉一下读者,也许我 ... -
多线程——休眠(sleep)
2011-12-14 10:46 18414先抛出一问题? 都说sleep与yield有哪些哪些的区 ... -
多线程——锁(lock)
2011-12-13 09:16 17221上一讲《多线程——同步(synchronized)下》 ... -
多线程——同步(synchronized)下
2011-12-12 16:12 4110接着上一讲《多线程— ... -
多线程——同步(synchronized)上
2011-12-12 12:20 4966多线程——同步(synchro ... -
多线程——状态转换
2011-12-11 12:18 3908多线程——状态转换 线程可以分为4个状态: New( ... -
实现一个简单的多线程
2011-12-11 10:55 5193一、定义线程 1、扩 ... -
Java线程及线程池专题
2011-12-09 17:18 10015Java多线程及线程池专题 第一部分:介绍多线程 ... -
(更新时间18号10:42)(原创)移动系统上线,全程经验分享
2011-10-17 12:22 2917移动系统上线,全程经验分享 时间:2011-10-18到20 ... -
(转载)Weblogic 各种版本下载
2011-10-16 23:09 4923Weblogic 各种版本下载 http://dev2d ... -
(入门培训)第一章:java开发工具与环境搭建
2011-10-16 22:36 1475java开发工具汇总 开发工具表: JDK 核心包 J ... -
我的Java学习推荐书目(转载)
2011-06-22 17:15 1033一直有这么个想法,列 ...
相关推荐
### 精通Java集合框架——List, Set, Map #### 概述 Java集合框架是一种高度抽象且灵活的数据组织工具,它通过一系列接口来定义不同类型的数据容器,并提供了丰富的操作这些容器的方法。本文将深入探讨Java集合...
【JAVA试题0618——.doc】是一个包含多种Java相关知识的问题集,涵盖了面向对象、I/O流、集合框架、EJB、HTTP协议、JSP、数据库操作、邮件发送、JNDI、JMS、事务管理和WebLogic Server等多个方面。以下是这些问题的...
1. **集合接口**:Java集合框架主要由两种接口构成——List(列表)和Set(集)。List接口允许元素有顺序,并且可以包含重复元素,如ArrayList和LinkedList。Set接口不允许重复元素,如HashSet和TreeSet。 2. **Map...
尽管在Java集合框架中,HashMap和HashSet更为常见,但Hashtable因其线程安全的特性在多线程环境中仍有一定应用。 接着,`StringStack1.java`可能定义了一个名为StringStack的类,这个类实现了栈的基本操作。栈是一...
Java EE API 整理主要涉及的是Java集成框架中的核心组件——集合框架。集合框架是Java编程语言中的一个重要组成部分,它提供了存储和管理对象的方式。在Java 2之前,也就是Java 1时代,集合框架并不完善,仅有一些...
Java集合框架是Java编程语言中处理数据结构的一个强大工具包,它提供了一系列灵活高效的接口和实现来帮助开发者管理数据。本篇文章将重点介绍Java中常用的集合类——`Collection`和`Map`及其相关子类,并探讨它们...
本文将围绕“张孝祥Java面试技巧”这一主题,深入探讨Java集合框架的重要组成部分——`map`、`set`、`list`,以及它们在Java中的实现方式和应用场景,帮助读者在面试中更好地展现自己的专业素养。 #### Collection...
Java集合框架主要由两个核心接口——`Collection`和`Map`构建。`Collection`接口又派生出三个子接口:`Set`、`List`和`Queue`。而`Map`接口则是独立的一类,用于存储键值对。 `Set`接口代表无序且不允许元素重复的...
以上内容涵盖了Java集合框架的基础知识,包括Collection接口、Set接口、List接口、Map接口的理解和使用,以及泛型、集合与数组的转换、集合的遍历和复制等重要概念。在实际开发中,掌握这些知识对于编写高效、安全的...
3. 泛型:泛型增强了Java集合框架,可以避免类型转换的麻烦,提高代码的类型安全。 三、高级特性篇 1. 内存管理与垃圾回收:理解Java内存模型,了解堆内存、栈内存以及垃圾回收机制。 2. 多线程:掌握线程的创建、...
Java容器,主要包括集合框架中的Set、List、Map和Queue接口,它们是Java编程中处理数据的重要工具。下面将对这些接口及其常见的实现类进行详细解释。 1. **Set接口**: Set接口代表一个无序且不允许重复元素的集合...
│ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分线程.mp4 │ Java面试题14.线程并发库和线程池...
3. **ArrayList与LinkedList**:两者都是Java集合框架中的列表实现。ArrayList基于动态数组,适合频繁的随机访问,但插入和删除效率较低。LinkedList基于链表结构,插入和删除操作快速,但随机访问性能较差。 4. **...
Java集合框架是Java编程语言中一个非常重要的组成部分,它提供了一种高效且灵活的方式来存储和操作数据。在Java中,集合被分为两类:单列集合(Collection)和双列集合(Map)。本笔记将深入探讨这两类集合及其相关...
- **Collection**:Java集合框架的核心接口之一,是所有集合类的父接口。 - **Collections**:提供了一系列静态方法用于操作集合,例如排序、查找等。 ### 11. `&&`与`&` #### 知识点说明: - **逻辑运算符**:`&&...
随着 Java 2 的发布,一个新的数据结构框架——集合框架(Collection Framework)被引入。集合框架提供了更加灵活和高效的数据结构实现,包括 `List`、`Set` 和 `Map` 接口以及它们的具体实现类,如 `ArrayList`、`...
在这个课件中,我们主要关注的是Java编程语言中的一个重要概念——集合框架。Java 集合框架是一个接口和类的集合,提供了存储、管理和操作对象的统一方式。 一、集合类型 Java 语言中的集合类型主要分为三类:Set、...
`Collection`是所有集合框架接口的根接口,表示一组不唯一的元素。而`Collections`是一个包含静态方法的类,提供了对集合操作的各种实用工具方法。 `assert`关键字在Java中用于断言,通常在测试和调试阶段使用,...
- **Collection**:Java集合框架的基础接口,包括`Set`和`List`等多种类型。 - **Collections**:提供了许多静态方法来操作`Collection`,如排序、搜索等。同时,它还提供了一些线程安全的集合类。 ### 8. HashMap...