欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于Java中最常用的集合类框架之HashMap(详解)

程序员文章站 2023-12-20 10:34:28
一、hashmap的概述 hashmap可以说是java中最常用的集合类框架之一,是java语言中非常典型的数据结构。 hashmap是基于哈希表的map接口实现的,此...

一、hashmap的概述

hashmap可以说是java中最常用的集合类框架之一,是java语言中非常典型的数据结构。

hashmap是基于哈希表的map接口实现的,此实现提供所有可选的映射操作。存储的是对的映射,允许多个null值和一个null键。但此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

除了hashmap是非同步以及允许使用null外,hashmap 类与 hashtable大致相同。

此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代collection 视图所需的时间与 hashmap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

hashmap 的实例有两个参数影响其性能:初始容量 和加载因子。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

通常,默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 hashmap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。

注意,此实现不是同步的。 如果多个线程同时访问一个hashmap实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。这通常是通过同步那些用来封装列表的 对象来实现的。但如果没有这样的对象存在,则应该使用{@link collections#synchronizedmap collections.synchronizedmap}来进行“包装”,该方法最好是在创建时完成,为了避免对映射进行意外的非同步操作。

map m = collections.synchronizedmap(new hashmap(...)); 

二、构造函数

hashmap提供了三个构造函数:

hashmap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 hashmap。

hashmap(int initialcapacity):构造一个带指定初始容量和默认加载因子 (0.75) 的空 hashmap。

hashmap(int initialcapacity, float loadfactor):构造一个带指定初始容量和加载因子的空 hashmap。

这里提到了两个参数:初始容量,加载因子。这两个参数是影响hashmap性能的重要参数,其中容量表示哈希表中桶的数量,初始容量是创建哈希表时的容量,加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是o(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。系统默认负载因子为0.75,一般情况下我们是无需修改的。

hashmap是一种支持快速存取的数据结构,要了解它的性能必须要了解它的数据结构。

三、数据结构

基于Java中最常用的集合类框架之HashMap(详解)

我们知道在java中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,hashmap也是如此。实际上hashmap是一个“链表散列”,如下是它数据结构:

// entry是单向链表。 它是 “hashmap链式存储法”对应的链表。 
// 实现了map.entry接口,即getkey(),getvalue(),setvalue(v value),equals(object o),hashcode()这些函数 
static class entry implements map.entry { 
 final k key; 
 v value; 
 // 指向下一个节点 
 entry next; 
 final int hash; 
 
 // 构造函数
 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 
 entry(int h, k k, v v, entry n) { 
  value = v; 
  next = n; 
  key = k; 
  hash = h; 
 } 
 
 public final k getkey() { 
  return key; 
 } 
 public final v getvalue() { 
  return value; 
 } 
 public final v setvalue(v newvalue) { 
  v oldvalue = value; 
  value = newvalue; 
  return oldvalue; 
 } 
 // 判断两个entry是否相等 
 // 若两个entry的“key”和“value”都相等,则返回true。 
 // 否则,返回false 
 public final boolean equals(object o) { 
  if (!(o instanceof map.entry)) 
   return false; 
  map.entry e = (map.entry)o; 
  object k1 = getkey(); 
  object k2 = e.getkey(); 
  if (k1 == k2 || (k1 != null && k1.equals(k2))) { 
   object v1 = getvalue(); 
   object v2 = e.getvalue(); 
   if (v1 == v2 || (v1 != null && v1.equals(v2))) 
    return true; 
  } 
  return false; 
 } 
 // 实现hashcode() 
 public final int hashcode() { 
  return (key==null ? 0 : key.hashcode()) ^ 
    (value==null ? 0 : value.hashcode()); 
 } 
 public final string tostring() { 
  return getkey() + "=" + getvalue(); 
 } 
 // 当向hashmap中添加元素时,绘调用recordaccess()。 
 // 这里不做任何处理 
 void recordaccess(hashmap m) { 
 } 
 // 当从hashmap中删除元素时,绘调用recordremoval()。 
 // 这里不做任何处理 
 void recordremoval(hashmap m) { 
 } 
}

从上图我们可以看出hashmap底层实现还是数组,只是数组的每一项都是一条链。其中参数initialcapacity就代表了该数组的长度。下面为hashmap构造函数的源码:

// 找出“大于capacity”的最小的2的幂,使hash表的容量保持为2的次方倍
 // 算法的思想:通过使用逻辑运算来替代取余,这里有一个规律,就是当n为2的次方(power of two),那么x%n==x&(n-1)。
 static final int tablesizefor(int cap) {
  int n = cap - 1;
  n |= n >>> 1; // >>> 无符号右移,高位补0
  n |= n >>> 2; // a|=b的意思就是把a和b按位或然后赋值给a
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n + 1;
 }
 // 构造一个带指定初始容量和加载因子的空hashmap
 public hashmap(int initialcapacity, float loadfactor) {
  if (initialcapacity < 0)
   throw new illegalargumentexception("illegal initial capacity: " + initialcapacity);
  if (initialcapacity > maximum_capacity)
   initialcapacity = maximum_capacity;
  if (loadfactor <= 0 || float.isnan(loadfactor))
   throw new illegalargumentexception("illegal load factor: " + loadfactor);
  this.loadfactor = loadfactor;
  this.threshold = tablesizefor(initialcapacity);
 }
 // 构造一个带指定初始容量和默认加载因子(0.75)的空 hashmap
 public hashmap(int initialcapacity) {
  this(initialcapacity, default_load_factor);
 }
 // 构造一个具有默认初始容量 (16)和默认加载因子 (0.75)的空 hashmap
 public hashmap() {
  this.loadfactor = default_load_factor; // all other fields defaulted
 }
 // 构造一个映射关系与指定 map相同的新 hashmap,容量与指定map容量相同,加载因子为默认的0.75
 public hashmap(map m) {
  this.loadfactor = default_load_factor;
  putmapentries(m, false);
 } 

从源码中可以看出,每次新建一个hashmap时,都会初始化一个table数组。table数组的元素为entry节点。

// entry是单向链表。 
 // 它是 “hashmap链式存储法”对应的链表。 
 // 它实现了map.entry 接口,即实现getkey(), getvalue(), setvalue(v value), equals(object o), hashcode()这些函数 
 static class entry implements map.entry { 
  final k key; 
  v value; 
  // 指向下一个节点 
  entry next; 
  final int hash; 
   // 构造函数。 
  // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 
  entry(int h, k k, v v, entry n) { 
   value = v; 
   next = n; 
   key = k; 
   hash = h; 
  } 
  ......
 }

其中entry为hashmap的内部类,它包含了键key、值value、下一个节点next,以及hash值,这是非常重要的,正是由于entry才构成了table数组的项为链表。

以上这篇基于java中最常用的集合类框架之hashmap(详解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。

上一篇:

下一篇: