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流程

  1. 对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位,这样计算出来的整型值将“具有”高位和低位的性质

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

get流程

  1. get对key hash,找到数组角标(indexfor())
  2. 如果hash相同key相同就找到了
  3. 如果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<Integer,Boolean>的时候使用,效率较高。
  • SparseLongArray: 当map的结构为Map<Integer,Long>的时候使用,效率较高。
  • LongSparseArray: 当map的结构为Map<Long,Value>的时候使用,效率较高。
  • 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

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) 的值表示经过散列函数计算得到的散列值。

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

  1. 散列函数计算得到的散列值是一个非负整数;
  2. 如果 key1 = key2,那 hash(key1) == hash(key2);
  3. 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)

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

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

散列冲突

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

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

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

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

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

如何设计散列函数?

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

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

装载因子过大了怎么办?

装载因子越大,说明散列表中的元素越多,空闲位置越少,散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链,查找的过程也会因此变得很慢。 扩容解决 实际上,对于动态散列表,随着数据的删除,散列表中的数据会越来越少,空闲空间会越来越多。

避免低效地扩容 我举一个极端的例子,如果散列表当前大小为 1GB,要想扩容为原来的两倍大小,那就需要对 1GB 的数据重新计算哈希值,并且从原来的散列表搬移到新的散列表,听起来就很耗时,是不是? 为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成。当装载因子触达阈值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中。

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

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

部分内容摘抄至极客时间《数据结构与算法之美》