`
greenwen
  • 浏览: 220412 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

HashMap实现原理

    博客分类:
  • java
 
阅读更多
1.HashMap的数据结构

   数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:



从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

  HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

  首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

2.HashMap的存取实现
     既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

//存储时:
int hash = key.hashCode();// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

//取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];


   到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

    疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?

  这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。

  当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。



3.解决hash冲突的办法
1.开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
2.再哈希法
3.链地址法
4.建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。


4.实现自己的HashMap

public class Entry<K,V>{
    final K key;
    V value;
    Entry<K,V> next;//下一个结点
 
    //构造函数
    public Entry(K k, V v, Entry<K,V> n) {
        key = k;
        value = v;
        next = n;
    }

    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 Entry))
            return false;
        Entry e = (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();
    }

}



//保证key与value不为空
public class MyHashMap<K, V> {
    private Entry[] table;//Entry数组表
    static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度
    private int size;

    // 构造函数
    public MyHashMap() {
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        size = DEFAULT_INITIAL_CAPACITY;
    }

    //获取数组长度
    public int getSize() {
        return size;
    }
    
    // 求index
    static int indexFor(int h, int length) {
        return h % (length - 1);
    }

    //获取元素
    public V get(Object key) {
        if (key == null)
            return null;
        int hash = key.hashCode();// key的哈希值
        int index = indexFor(hash, table.length);// 求key在数组中的下标
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            Object k = e.key;
            if (e.key.hashCode() == hash && (k == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

    // 添加元素
    public V put(K key, V value) {
        if (key == null)
            return null;
        int hash = key.hashCode();
        int index = indexFor(hash, table.length);

        // 如果添加的key已经存在,那么只需要修改value值即可
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            Object k = e.key;
            if (e.key.hashCode() == hash && (k == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;// 原来的value值
            }
        }
        // 如果key值不存在,那么需要添加
        Entry<K, V> e = table[index];// 获取当前数组中的e
        table[index] = new Entry<K, V>(key, value, e);// 新建一个Entry,并将其指向原先的e
        return null;
    }

}



public class MyHashMapTest {

    public static void main(String[] args) {

        MyHashMap<Integer, Integer> map = new MyHashMap<Integer, Integer>();
        map.put(1, 90);
        map.put(2, 95);
        map.put(17, 85);
    
        System.out.println(map.get(1));
        System.out.println(map.get(2));
        System.out.println(map.get(17));
        System.out.println(map.get(null));
    }
}


source:http://www.cnblogs.com/xwdreamer/archive/2012/05/14/2499339.html
  • 大小: 49 KB
分享到:
评论

相关推荐

    hashmap实现原理

    在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...

    基于HashMap的用户标签处理兼Java中HashMap实现原理研究.pdf

    "基于HashMap的用户标签处理兼Java中HashMap实现原理研究" 本文研究了基于HashMap的用户标签处理方法,并对Java中HashMap的实现原理进行了深入研究。HashMap是一种高效的数据结构,可以快速地存储和检索数据。本文...

    hashmap实现原理.pdf

    hashmap实现原理.pdf

    Jdk1.8中的HashMap实现原理.docx

    《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...

    Jdk1.8中的HashMap实现原理.pdf

    总结起来,JDK1.8中的HashMap实现原理主要包括以下几个要点: 1. 链表散列结构:数组+链表,链表用于处理哈希碰撞。 2. 红黑树优化:当链表长度超过8时,转换为红黑树,减少查找、插入和删除的时间复杂度。 3. 内部...

    Jdk1.8 HashMap实现原理详细介绍

    以下是对JDK 1.8 HashMap实现原理的详细解释。 首先,HashMap是一个基于哈希表的数据结构,它实现了Map接口。它不保证映射的顺序,并且是非同步的。这意味着在多线程环境中,如果不进行同步控制,可能会出现并发...

    详解Java HashMap实现原理

    以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个...

    Java8 HashMap的实现原理分析

    Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧

    深入解析java HashMap实现原理

    综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...

    HashMap底层原理.md

    HashMap底层原理.md

    源码解析jdk8.0集合:HashMap的底层实现原理.pdf

    根据提供的文件信息,以下是对JDK 8.0中HashMap实现原理的详细知识点介绍: 1. HashMap概述 HashMap是Java集合框架的一部分,它实现了Map接口,用于存储键值对。其核心特点在于基于哈希表的映射机制,能够通过键...

    源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf

    ### JDK 7.0集合系列解析之HashMap实现原理 #### 一、HashMap概述 HashMap是Java集合框架中Map接口的典型实现之一,主要用于存储键值对(Key-Value)数据。其特性如下: - 线程不安全,方法为非同步方法,因此多...

    深入Java集合学习系列:HashMap的实现原理

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

    HashMap原理的深入理解

    HashMap原理的深入理解 HashMap是基于哈希表的Map接口的非同步实现,提供了所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久...

    java HashMap原理分析

    Java HashMap原理分析 Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向...

    HashMap底层原理

    HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...

    Java HashMap实现原理分析(一)

    HashMap的实现原理基于哈希表,它的核心是通过哈希函数将键(key)映射到一个数组的特定位置,从而实现快速访问。本文将深入解析HashMap的put和get操作的内部机制。 首先,HashMap的底层数据结构是一个动态扩容的...

    HashMap的实现原理

    ### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...

Global site tag (gtag.js) - Google Analytics