热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

源码分析HashMap

 1、数据结构:数组+链表 成员变量,数组table[bucketIndex]newEntry(hash,key,value,e);transientEntry[]tab

 

1、数据结构:数组+链表 

//成员变量,数组 table[bucketIndex] = new Entry(hash, key, value, e);
transient Entry[] table;
//内部类,链表
static class Entry implements Map.Entry {
final K key;
V value;
//链表指向下个元素
Entry next;
final int hash;
/**
* Creates new entry.
*/
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;
}
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;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap m) {
}
}

 

2、put存值

     向链表头部插入元素,数组元素即为头。

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//计算hash值
int hash = hash(key.hashCode());
//计算数组下标
int i = indexFor(hash, table.length);
for (Entry 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 hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算数组下标
static int indexFor(int h, int length) {
//保证结果的最大值是length-1,不会产生数组越界问题。
return h & (length-1);
}
//向链表头部插入元素
void addEntry(int hash, K key, V value, int bucketIndex) {
//获取table[i]的对象e
Entry e = table[bucketIndex];
//将table[i]的对象修改为新增对象,让新增对象的next指向e。
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
//超过阀值,生成新的Entry[]数组。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//最大容量:static final int MAXIMUM_CAPACITY = 1 <<30;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
//生成新的数组
table = newTable;
//阀值等于新的容量乘以加载因子(默认0.75)
threshold = (int)(newCapacity * loadFactor);
}

 

 

 3、get取值

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//hash和key值都相等
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

 

4、相关知识

        Hash,一般翻译做“散列”,也有直接音译为&#8221;哈希&#8221;的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。

        java两个对象值相同(x.equals(y) == true),则一定有相同的hash code。当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象equals必须具有相等的哈希码。hashCode相等对象未必相等。

        数组的特点是空间连续(大小固定)、寻址迅速,但是插入和删除时需要移动元素,所以查询快,增加删除慢。链表恰好相反,可动态增加或减少空间以适应新增和删除元素,但查找时只能顺着一个个节点查找,所以增加删除快,查找慢。哈希表综合2者优点,但实际上查找肯定没有数组快,插入删除没有链表快,一种折中的方式。

      参考:http://www.cnblogs.com/hzmark/archive/2012/12/24/HashMap.html


推荐阅读
  • 深入解析 Android 中的 ActivityGroup 实现
    本文详细探讨了如何在 Android 应用中使用 ActivityGroup 来实现类似微博客户端主界面的效果,并分析了 TabActivity 的局限性,推荐使用更为灵活的 ActivityGroup 方案。 ... [详细]
  • 本文探讨了如何利用 Application 对象在 PHP 应用程序中共享数据,特别是在多用户环境中保持数据的一致性和安全性。文章还介绍了 Application 对象的基本结构、方法和事件,并提供了实际应用示例。 ... [详细]
  • 本文介绍了如何在Java中使用`JCheckBoxMenuItem.setMnemonic()`方法,并提供了多个实际应用的代码示例。 ... [详细]
  • Lua基本语法lua与C#的交互(相当简单详细的例子)
    lua脚本与C#的交互本文提供全流程,中文翻译。Chinar坚持将简单的生活方式,带给世人!(拥有更好的阅读体验——高分辨率用户请根据需求调整网页缩放比例)1LuaAndC#——L ... [详细]
  • 利用Executor框架管理线程池
    本文介绍了如何使用Executor框架来管理和创建线程池,包括不同的线程池类型及其应用场景,以及如何通过Executors工厂类创建不同类型的Executor实例。 ... [详细]
  • 本文提供了一个Android应用中用于抓取网页信息并下载图片的示例代码。通过该代码,开发者可以轻松实现从指定URL获取网页内容及其中的图片资源。 ... [详细]
  • 深入解析达内Java基础练习题
    本文精选了几道典型的Java基础题目,旨在帮助学习者巩固基础知识,提升编程技能。通过这些题目,你可以检验自己的Java基础掌握程度。 ... [详细]
  • 【Java数据结构和算法】008栈
    目录0、警醒自己一、栈的应用场景和介绍1、栈的应用场景一个实际的场景:我的思考:2、栈的介绍入栈演示图:出栈演示图 ... [详细]
  • 初学者必备:iBATIS入门指南与常见问题解决
    本文旨在为iBATIS初学者提供一份详细的入门指南,并针对官方文档中示例不足的问题提出解决方案。适合零基础学习者。 ... [详细]
  • 本文通过对OkHttp源码的详细解读,旨在帮助读者理解其核心执行流程,特别是同步与异步请求的处理方式。文中不仅涵盖了基本的使用示例,还深入探讨了OkHttp的核心功能——拦截器链的工作原理。 ... [详细]
  • AOP底层技术CGLIB示例 ... [详细]
  • 深入解析线程池的工作原理与实际应用
    本文详细探讨了线程池的核心概念、工作原理及其在实际开发中的应用,包括不同类型的线程池创建方式及其适用场景。 ... [详细]
  • 本文档详细介绍了如何在Android应用中实现侧滑菜单(SlidingMenu)功能,包括设置侧边栏、全屏触摸模式以及初始化Fragment的具体步骤。 ... [详细]
  • 本文详细探讨Java中Scanner类的两个重要方法——nextInt()和nextDouble(),并通过实例代码演示如何使用这些方法来处理用户输入。 ... [详细]
  • 第三周课堂测试1、使用汇编语言编写指令时,用一些简单的容易记忆的符号来代替二进制指令,比机器语言更为方便,属于高级语言。(B ... [详细]
author-avatar
西单女孩超炫
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有