`
soleghost
  • 浏览: 41839 次
  • 性别: Icon_minigender_1
  • 来自: 未知
社区版块
存档分类
最新评论

hashmap学习

阅读更多

1.数据结构

数组+链表的形式    【】【】【】【】【】

                                     |       |       |       |       |

                                  【】【】【】【】【】

数组长度:固定,即初始化HashMap时的capacity。当需要数组长度时,会rehash,重新计算容器中所有值的位置

链表长度:可以扩展,即冲突的对象放入链表中

 

2.如何从map中寻找值

    public V get(Object key) {
        Object k = maskNull(key);
        int hash = hash(k);
        int i = indexFor(hash, table.length);
        Entry<K,V> e = table[i]; 
        while (true) {
            if (e == null)
                return null;
            if (e.hash == hash && eq(k, e.key)) 
                return e.value;
            e = e.next;
        }
    }

    static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

 a.计算hash值(计算hash值,采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用,且兼顾计算效率以及数据统计的特性)

 b.通过hash值和capcity作位运算,获取数组中的index

 c.在指定数组元素中,用equals索引链表,获得查询的值

 

 

3.几个变量

initialCapacity:初始化map中元素的个数的参数,不代表是最好map中最后设置的值

loadFactor:负载因子

capacity:Find a power of 2 >= initialCapacity,实际容量

threshold:capacity*loadFactor=threshold,当map中元素的数据>threshold时,capacity会double,然后会做最耗性能的resize

 

4.initialCapacity的参数值,一定要根据业务估算,否则可能会rehash,浪费性能

 

5.为何将capacity设为2的N次方?

因为java可以利用位运算作取模运算,提供运行速度

 

6.非线程安全的Map VS Collections.synchronizedMap

fail-fast机制(比如,循环遍历时,不能添加或者删除map中元素)

 

7.linkedHashMap VS LRU(最近最久未使用算法)

a.实现方式:HashMap的子类,利用双链表维持内部元素的关系

b.内部header、before、after3个指针引用

c.由于增加了维护链接列表的开支,其性能要比 HashMap 稍逊一筹,不过有一点例外:LinkedHashMap的迭代所需时间与其的所包含的元素成比例;而HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量(分配给Key空间的长度)成比例。一言以蔽之,随机存取用HashMap,顺序存取或是遍历用 LinkedHashMap。

d.缺省情况下,LinkedHashMap采取的更新策略是类似于队列的FIFO,如果你想实现更复杂的更新逻辑比如LRU(最近最少使用)等,将removeEldestEntry与accessOrder一起使用,就可以实现最基本的内存缓存。如果accessOrder被设置为true,则每次访问元素时,都将该元素移至head的前面,即链表的尾部。

 

8.WeakHashMap

a.强引用、软引用、弱引用、虚幻引用

b.WeakHashMap采用的策略是,只要作为key的对象已经不存在了(超出生命周期),就不会阻止垃圾收集器清空此条目,即使当前机器的内存并不紧张。

 

分享到:
评论

相关推荐

    马士兵老师HashMap学习笔记

    《马士兵老师HashMap学习笔记详解》 HashMap是Java编程语言中常用的一种数据结构,它提供了键值对(key-value pair)的存储功能,是基于哈希表实现的。马士兵老师的HashMap学习笔记深入剖析了这一核心组件的工作...

    algorithm004-01#algorithm004-01#HashMap学习总结1

    通过hash函数计算的结果与capacity-1进行且运算,得到buckets的index,若buckets[index]为空,则直接赋值,若不为空,首先查看首

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

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

    Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结

    Java集合专题总结:HashMap和HashTable源码学习和面试总结 本文总结了Java集合专题中的HashMap和HashTable,涵盖了它们的源码学习和面试总结。HashMap是一种基于哈希表的集合类,它的存储结构是一个数组,每个元素...

    深入解读大厂java面试必考点之HashMap全套学习资料

    本套学习资料全面涵盖了HashMap的深入解析,旨在帮助求职者掌握大厂面试中的核心知识点。 HashMap是基于哈希表实现的,其底层原理主要依赖于数组和链表。它提供了O(1)的平均时间复杂度进行插入、删除和查找操作。...

    学习笔记:三数组实现的HashMap

    "学习笔记:三数组实现的HashMap"这篇博客文章可能讨论了一种非标准但有趣的HashMap实现,使用了三个数组来代替标准的哈希表结构。这里我们将深入探讨这种三数组实现HashMap的原理和可能的优势。 1. **基本概念**:...

    HashMap类.rar

    通过分析源码,开发者可以深入理解哈希表的工作原理,学习如何在易语言中实现高效的数据结构,这对于提升程序性能和优化内存管理至关重要。同时,这也为自定义数据结构或实现其他哈希表相关的功能提供了基础。

    易语言HashMap类

    易语言HashMap类是一种在易语言编程环境中实现的高效数据结构,它主要用于存储键值对(key-value pairs),提供快速的数据存取。...通过深入学习和实践,开发者可以更好地利用HashMap类解决实际编程问题。

    hashmap的C++实现

    hashmap的C++实现,对于学习C++方面的很有用

    HashMap详解(通俗易懂)

    这个文档“ HashMap详解(通俗易懂)”很好的阐述了hashmap的底层数据结构示意,希望对学习java的人有帮助

    HashMap_学习

    这是一套PPT,讲述的内容是Java的JDK中内置的几种常用的集合框架工具类的知识,重点讲解HashMap,因为不让上传视频,就先传个PPT试试;

    全手写HashMap精简版Demo 可直接允许查看效果

    在学习过程中,可以重点关注哈希函数的设计、链表的插入与查找以及扩容的实现,这些都是HashMap性能的关键因素。同时,它也可以作为进一步研究和优化哈希表的基础,例如探索更高效的哈希算法或者优化扩容策略。

    解析HashMap.md

    黑马程序员HashMap的笔记,面试必问,笔记很好,内容言简意赅,看完收获很多,希望能帮助大家的学习

    Java-HashMap.rar_hashmap_java hashmap

    在Java编程语言中,`HashMap`是`...在学习和使用`HashMap`时,不仅要掌握其基本用法,还要了解其内部工作原理,包括哈希函数、哈希冲突的解决策略(开放寻址法或链地址法),以及如何调整容量和负载因子以优化性能。

    asp hashmap,arraylist实现

    标题中的“asp hashmap,arraylist实现”指的是在ASP(Active Server Pages)编程中使用HashMap和ArrayList这两种数据结构的具体应用。...学习和理解这些内容对于提升ASP.NET开发中的数据管理和效率至关重要。

    hashMap利用iterator迭代器迭代元素方法

    无论是在学习Java基础还是进行实际开发,掌握`HashMap`的迭代方法都是非常重要的技能。通过`entrySet()`、`keySet()`或`values()`,我们可以根据需求选择合适的迭代方式,从而高效地遍历和处理`HashMap`中的数据。

    hashMap1.8源码

    HashMap是Java编程语言中最常用的集合类之一,它提供了一种基于键值对(key-value pair)的数据存储方式,具有高效查找、插入和删除操作。...对于学习者来说,阅读源码并结合实践是掌握HashMap的最好方式。

    HashMap CRUD操作

    在`Javase_product_HashMap`这个压缩包中,可能包含了实现以上操作的Java源代码示例,供学习者参考和实践。通过这个例子,初学者可以更好地理解HashMap的基本操作以及在实际问题中的应用。同时,了解并掌握HashMap的...

    hashmap.zip

    在这个压缩包文件"hashmap.zip"中,包含了关于HashMap的案例、资料、讲义等资源,是深入学习HashMap的好材料。 首先,我们需要了解HashMap的基本概念。HashMap是一个散列容器,内部通过数组加链表的方式实现。每个...

    用HashMap模拟一个网上购物车

    此外,我们还将学习如何使用`Scanner`类从键盘接收用户输入。 #### 二、实验需求分析 根据题目要求,我们需要完成以下任务: 1. 创建一个包含五本书信息的数据结构。 2. 每本书的信息包括书名(名称)、单价以及...

Global site tag (gtag.js) - Google Analytics