文档章节

HashMap存储详解

小车车
 小车车
发布于 2017/05/25 10:10
字数 536
阅读 4
收藏 0

1.存储概念讲解

        面试的时候一般会问HashMap里的数据是怎么存储的?怎么存储的和存储结构是不一样的,如果回答用Entry数组来存储的是有问题。首先你应该向面试官问,是Java 7 还是Java 8 ,因为这两者是不一样的,一个是Entry数组实现的,一个是用二叉树Node来实现的。

2.HashMap的实现原理

    简单地说,HashMap就是将key做hash算法,然后将hash值映射到内存地址,直接取得key所对应的数据。在Java 7 中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。

    Java 7 源码:代码中 h ^= k.hashCode();来获取Object的hashcode值。

final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // 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保存值

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        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;
    }

     通过调用hash函数int hash = hash(key);  获取hashcode,然后通过addEntry(hash, key, value, i);方法保存到Entry数组中。

    补充:Java8的源码。

    获取hashcode:

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

3.hash冲突问题

    那就要深入HashMap的内部,它的内部维护着一个Entry数组,每一个Entry表项包括key、value、next和hash几项。这里要注意的是next部分,它指向了另外一个Entry。进一步阅读HashMap的put()方法,可以看到当put操作有冲突时,新的Entry依然会被安放在对应的索引下标内,并替换原有的值。同时,为了保证旧值不丢失,会将新的Entry的next指向旧值。这便实现了一个数组索引空间内存放多个值项。

© 著作权归作者所有

小车车
粉丝 5
博文 95
码字总数 104288
作品 0
深圳
程序员
私信 提问
Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法 上一篇文章我们研究了set接口下的几个容器,由于其Set集合...

贾浩v
2017/10/19
0
0
ConcurrentMap的详解

ConcurrentHashMap默认初始大小 16,临界值:12:基数:0.75 1.ConcurrentHashMap是一个线程安全的hashMap。相对hashMap多出以下一些特殊属性: //默认能够同时运行的线程数目 static final...

Sheamus
2016/02/19
27
0
详解HashMap,Hashtable,LinkedHashMap,TreeMap的异同点

Map Map是是一种数据结构,它是把数据按照key-value键值对的形式保存起来,一般来说,Map的定义是key是独一无二的,即存在map中的各个键一定是不能相同的。当然,对于一般的基本数据类型和S...

断桥残雪断桥残雪
2015/08/14
0
0
Redis原理详解

数据类型 Redis最为常用的数据类型主要有以下五种: String Hash List Set Sorted set 在具体描述这几种数据类型之前,我们先通过一张图了解下Redis内部内存管理中是如何描述这些不同数据类型...

2k10
2016/08/25
200
0
mybatis缓存机制详解(一)——Cache

缓存概述 在mybatis中,缓存的功能由根接口Cache(org.apache.ibatis.cache.Cache)定义。整个体系采用装饰器设计模式,数据存储和缓存的基本功能由PerpetualCache(org.apache.ibatis.cache...

拉风小野驴
2016/02/24
3.1K
1

没有更多内容

加载失败,请刷新页面

加载更多

Issue和PR标签(Kubernetes社区Issue和PR标签解释)

一般标签 标签 含义 备注 good first issue 指示该issue适合由新贡献者参与 参照"help wanted"指导文档 help wanted 指示该issue需要帮助 必须满足"help wanted"指导文档 needs-kind 指示该i......

恋恋美食
51分钟前
1
0
Array数组操作

includes() 方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回 true,否则返回false。 Eg:error.message.includes('timeout'); 1、indexOfindexOf()方法返回在该数组中第一...

lslaiwy
今天
2
0
运行pipenv报错UnicodeDecodeError的问题

问题:运行pipenv就报错:UnicodeDecodeError: 'utf-8' codec can't decode ...... 环境:windows10,python 3.7.1 解决:因为升级了一次3.7.3恰好有出了这问题,结果绕了很多弯路,以为是p...

编程老陆
今天
0
0
Android7.1 recent过滤指定应用

systemui/recents/model/RecentsTaskLoadPlan.java 找到 preloadPlan方法 /* * Copyright (C) 2014 The Android Open Source Project * * Licensed under the Apache License, Version......

安卓工程师王恒
今天
2
0
为什么Map桶中个数超过8才转为红黑树

要弄明白这个问题,我们首先要明白为什么要转换,这个问题比较简单,因为Map中桶的元素初始化是链表保存的,其查找性能是O(n),而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候,...

xiaomin0322
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部