HashMap、lru、散列表-阿里云开发者社区

HashMap

HashMap的数据结构：HashMap实际上是一个数组和链表（“链表散列”）的数据结构。底层就是一个数组结构，数组中的每一项又是一个链表。
hashCode是一个对象的标识，Java中对象的hashCode是一个int类型值。通过hashCode来算出指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为O(1)，并且不同对象可以拥有相同的hashCode（hash碰撞）。发生碰撞后会把相同hashcode的对象放到同一个链表里，但是在数组大小不变的情况下，存放键值对越多，查找的时间效率也会降低
扩容可以解决该问题，而负载因子决定了什么时候扩容，负载因子是已存键值对的数量和总的数组长度的比值。默认情况下负载因子为0.75，我们可在初始化HashMap的时候自己修改。阀值 = 当前数组长度✖负载因子
hashmap中默认负载因子为0.75，长度默认是16，默认情况下第一次扩容判断阀值是16 ✖ 0.75 = 12；所以第一次存键值对的时候，在存到第13个键值对时就需要扩容了,变成16X2=32。

put流程

对key hash，二次hash，hash扰乱函数，减少hash碰撞

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}

获取对象的hashcode以后，先进行移位运算，然后再和自己做异或运算，即：hashcode ^ (hashcode >>> 16)，这一步甚是巧妙，是将高16位移到低16位，这样计算出来的整型值将“具有”高位和低位的性质

通过hash算出数组角标（indexfor（））
添加元素，看是否需要扩容，需要的话变数组变成原来的2倍，把旧的拷贝到新的数组上去，然后旧的指针指向新的。
如果key相同的覆盖；没有的话添加元素

get流程

get对key hash，找到数组角标（indexfor（））
如果hash相同key相同就找到了
如果hash相同key不相同，找链表的下一个（通过值找）

其他问题

1.7 和 1.8 数据结构有什么不同？
1.8 增加了转换为红⿊树
插⼊数据的⽅式
1.7 的链表从前⾯插⼊，1.8 的链表从后⾯插⼊
HashMap 什么时候会把链表转化为红⿊树？
链表⻓度超过 8 ，并且数组⻓度不⼩于 64
在 JDK1.8 版本中，为了对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

优化hashmap

HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。

ArrayMap是Android专门针对内存优化而设计的，用于取代Java API中的HashMap数据结构。为了更进一步优化key是int类型的Map，Android再次提供效率更高的数据结构SparseArray，可避免自动装箱过程。对于key为其他类型则可使用ArrayMap。HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的，而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存。

SparseBooleanArray: 当map的结构为Map的时候使用，效率较高。
SparseLongArray: 当map的结构为Map的时候使用，效率较高。
LongSparseArray: 当map的结构为Map的时候使用，效率较高。
ArraySet：和ArrayMap的目的类似，用来提高HashSet的效率。使用方法跟HashSet类似

ArrayMap的key是任意对象，list等等，一般是存一个键值，获取数据简单

map.keyAt(0)

map.valueAt(0)

ArrayMap的内部实现是两个数组，一个int数组是存储对象数据对应下标，一个对象数组保存key和value，内部使用二分法对key进行排序，所以在添加、删除、查找数据的时候，都会使用二分法查找，只适合于小数据量操作，通常情况下要比传统的HashMap慢，因为查找是用二分查找法搜索，添加和删除需要对数组进行添加和删除。
为了提高性能，该容器提供了一个优化：当删除key键时，不是立马删除这一项，而是留下需要删除的选项给一个删除的标记。该条目可以被重新用于相同的key,或者被单个垃圾收集器逐步删除完全部的条目后压缩。
为了减少频繁地创建和回收Map对象，ArrayMap采用了两个大小为10的缓存队列来分别保存大小为4和8的Map对象。为了节省内存有更加保守的内存扩张（扩容的少）以及内存收缩策略（gc的频繁（删除不用的空间，新的数组））
当mSize大于或等于mHashes数组长度时则扩容，完成扩容后需要将老的数组拷贝到新分配的数组，并释放老的内存。

当map个数满足条件 osize<4时，则扩容后的大小为4；
当map个数满足条件 4<= osize < 8时，则扩容后的大小为8；当map个数满足条件 osize>=8时，则扩容后的大小为原来的1.5倍；
可见ArrayMap大小在不断增加的过程，size的取值一般情况依次会是4，8，12，18，27，40，60

HashMap存对象

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。如果要用对象作为key的话需要重新该对象的equals方法和hashCode方法。

new一个新的对象时，地址变了，不能保证hash值和equals结果还是一样。所以取不到对应的value。

   Map<People,Integer> map = new HashMap<People, Integer>();
         map.put(new People("liu",18),5);
        People p = new People("liu",18);
        System.out.println(map.get(p));

LinkedHashMap

HashMap 底层是通过散列表这种数据结构实现的。而 LinkedHashMap 前面比 HashMap 多了一个“Linked”，这里的“Linked”是不是说，LinkedHashMap 是一个通过链表法解决散列冲突的散列表呢？

散列表中数据是经过散列函数打乱之后无规律存储的，LinkedHashMap是如何实现按照数据的插入顺序来遍历打印的呢？

LinkedHashMap 也是通过散列表和链表组合在一起实现的。实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。你可以看下面这段代码：

 
// 10是初始大小，0.75是装载因子，true是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
 
m.put(3, 26);
m.get(5);
 
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}

这段代码打印的结果是 1，2，3，5、

每次调用 put() 函数，往 LinkedHashMap 中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：

在第 8 行代码中，再次将键值为 3 的数据放入到 LinkedHashMap 的时候，会先查找这个键值是否已经有了，然后，再将已经存在的 (3,11) 删除，并且将新的 (3,26) 放到链表的尾部。所以，这个时候链表中的数据就是下面这样：

当第 9 行代码访问到 key 为 5 的数据的时候，我们将被访问到的数据移动到链表的尾部。所以，第 9 行代码之后，链表中的数据是下面这样：

从上面的分析，你有没有发现，按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统？实际上，它们两个的实现原理也是一模一样的。我也就不再啰嗦了。

LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。

因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或者跳表）结合在一起使用。

least recentlly use

最少最近使用算法，就是使用的LinkedHashMap

会将内存控制在一定的大小内, 这个最大值可以自己定，超出最大值时会自动回收。他内部是是一个LinkedHashMap存储外界的缓存对象，提供了get,put方法来操作，当缓存满了，lru会移除较早使用的缓存对象，把新的添加进来。
HashMap是无序的，而LinkedHashMap默认实现是按插入顺序排序的，怎么存怎么取。LinkedHashMap每次调用get(也就是从内存缓存中取图片)，则将该对象移到链表的尾端。调用put插入新的对象也是存储在链表尾端，这样当内存缓存达到设定的最大值时，将链表头部的对象（近期最少用到的）移除。
内存中使用LRUCache是最合适的。如果用HashMap来实现，不是不可以，但需要注意在合适的时候释放缓存，还得控制缓存的大小。

public class BitmapCache implements ImageCache {  
  
    private LruCache<String, Bitmap> mCache;  
  
    public BitmapCache() {  
    long maxSize = Runtime.getRuntime().maxMemory() / 8;
      //  int maxSize = 10 * 1024 * 1024;  
        mCache = new LruCache<String, Bitmap>(maxSize) {  
            @Override  
            protected int sizeOf(String key, Bitmap bitmap) {  
            //获取图片占用内存大小
                return bitmap.getRowBytes() * bitmap.getHeight();  
            }  
        };  
    }  
  
    @Override  
    public Bitmap getBitmap(String url) {  
        return mCache.get(url);  
    }  
  
    @Override  
    public void putBitmap(String url, Bitmap bitmap) {  
        mCache.put(url, bitmap);  
    }  
  
}

散列表

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表"

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

其中，参赛选手的编号我们叫作键（key）或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

时间复杂度

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)

然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

散列函数

散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

该如何构造散列函数呢？我总结了三点散列函数设计的基本要求：

散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

我来解释一下这三点。其中，第一点理解起来应该没有任何问题。因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数。第二点也很好理解。相同的 key，经过散列函数得到的散列值也应该是相同的。

第三点理解起来可能会有问题，我着重说一下。这个要求看起来合情合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。

散列冲突

开放寻址法
线性探测
我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突

散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

链表法
Java 中 LinkedHashMap 就采用了链表法解决冲突

如何设计散列函数？

如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？

首先，散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽（链表）里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

装载因子过大了怎么办？

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

扩容解决

实际上，对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。

避免低效地扩容

我举一个极端的例子，如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表，听起来就很耗时，是不是？

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。

当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

这期间的查询操作怎么来做呢？对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。

HashMap、lru、散列表

HashMap

put流程

get流程

其他问题

优化hashmap

HashMap存对象

LinkedHashMap

least recentlly use

散列表

散列函数

散列冲突

如何设计散列函数？

装载因子过大了怎么办？

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HashMap、lru、散列表

HashMap

put流程

get流程

其他问题

优化hashmap

HashMap存对象

LinkedHashMap

least recentlly use

散列表

散列函数

散列冲突

如何设计散列函数？

装载因子过大了怎么办？

热门文章

最新文章

相关电子书