NoSQLHashMap的落实同优化

HashMap的优化以及履行

正文是依据作者在github上的Android
问题交流讨论坛提问要发的均等篇稿子,也是团结早打算开坑的相同首稿子。文章首先介绍了hashMap的一些基本知识,然后介绍了它们以JDK8下的实现原理,最后要介绍了几只面试中拍卖非常数额的法门,文章于长,我啊描绘了长期,希望各位能够读了并发表意见。

Android 题交流讨论坛是开源达人 Trinea
在gitHub上组建的一个讨论组织,那里的咨询以及答都特别靠谱。

HashMap的复杂度

要是图是ArrayList/LinkedList/HashMap三只数据结构的复杂度对比,可以看到HashMap整体达标性都不行不易,但是不安定,为O(N/Buckets),N就是以数组中绝非发打的元素,Buckets是因撞击时有发生的链表。

获取 查找 添加/删除 空间
ArrayList O(1) O(1) O(N) O(N)
LinkedList O(N) O(N) O(1) O(N)
HashMap O(N/Bucket_size) O(N/Bucket_size) O(N/Bucket_size) O(N)

流动:发生相撞实际上是深稀有的,所以N/Bucket_size约等于1

HashMap是对Array与Link的妥协处理,Array与Link可以说凡是零星单速度方向的无限,Array注重于数据的得到,而拍卖修改(添加/删除)的效率非常小;Link由于是每个对象还保持着下一个靶的指针,查找某个数要遍历之前所有的数码,所以效率比小,而在改动操作着比较快。

复杂度是哪些考察之?

对数据结构,在岁月达我们用考察Acessing ,Search,
Deletion/Insertion的平分与无限差之复杂度。在空间上,我们而考虑保护这数据结构所占据的内存空间。

泛的数据结构与排序的复杂度都以这里

HashMap的实现

本文为JDK8的API实现进行辨析

1. 哟是hash,什么是碰上?

  • Hash:是相同种信息摘要算法,一般用于证明完整性,它还叫哈希,或者散列,但是它们莫是加密。我们平常采用的MD5,SHA1,SSL中之公家钥验证都属于Hash算法,通过输入key进行Hash计算,就好获key的HashCode(),比如我们由此校验MD5来说明文件的完整性。

  • 碰撞:好的Hash算法可以生计算几乎有独一无二之HashCode,如果出现了重的hashCode,就如作碰撞;

尽管是MD5这样出色之算法也会起撞击,即有限单例外的key也来或变化相同之MD5。

2. HashMap中是什么样贯彻写副与读取的?

HashMap实现了Map接口,保存在K-V这样的联谊。我们为put操作为例

2.1. 对key进行Hash计算

以JDK8遇,由于使用了开门红黑树来处理好之链表开销,所以hash这边可以进一步节能了,只所以计算hashCode并活动至小就可了

static final int hash(Object key) {
    int h;
    //计算hashCode,并无符号移动到低位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

选举个例: 363771819^(363771819 >>> 16)

0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)

然做足兑现了大身价进一步均匀地混到一块儿,详见这里

下为闹几乎独常因此之哈希码(hashCode)的算法。

  1. Object类的hashCode.
    返回对象的经过处理后底内存地址,由于每个对象的内存地址都不等同,所以哈希码也非同等。这个是native方法,取决于JVM的中间设计,一般是某种C地址的皇。
  2. String类的hashCode.
    根据String类包含的字符串的情,根据同样种独特算法返回哈希码,只要字符串的内容相同,返回的哈希码也同等。
  3. Integer等包裹类,返回的哈希码就是Integer对象里所涵盖的要命整数的数值,例如Integer
    i1=new Integer(100),i1.hashCode之价就是是100
    。由此可见,2只同大小的Integer对象,返回的哈希码也如出一辙。
  4. int,char这样的底蕴类,它们不欲hashCode,如果急需仓储时,将拓展活动装箱操作,计算方法和齐。

2.2. 得到眼前之职

计了Hash,我们今天若拿它们插入数组中了

i = (tab.length - 1) & hash;

透过各类运算,确定了当前底职务,因为HashMap数组的大小总是2^n,所以实际的运算就是
(0xfff…ff) & hash
,这里的tab.length-1相当给一个mask,滤掉了盖当前长位之hash,使每个i都能够插入到数组中。

2.3. 生成包装类

这个目标是一个打包类,Node<K,V>,内部发生key,value,hash还有next,可以关押下她是一个链表。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //getter and setter .etc.
}

2.4. 插包装类至数组

(1). 如果输入当前之岗位是拖欠的,就栽上,如图,左为插入前,右为插入后

0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> null   i - > new node
|           |
n -> null   n - > null

(2).
如果手上位置已经闹矣node,且其来了拍,则新的放前面,旧的搁后面,这叫做链地址法处理闯。

0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> old    i - > new - > old
|           |
n -> null   n - > null

咱得以窥见,失败的hashCode算法会导致HashMap的性质由数组下降呢链表,所以想要避起撞击,就设增长hashCode结果的均匀性。当然,在JDK8饱受,采用了吉祥黑二交叉树进行了处理,这个我们后详细介绍。

什么是Hash攻击?

通过请大量key不同,但是hashCode相同的数,让HashMap不断发生冲击,硬生生的成了SingleLinkedList

0
|
1 -> a ->b -> c -> d(撞!撞!撞!复杂度由O(1)变成了O(N))
|
2 -> null(本应该均匀分布,这里却是空的)
|
3 -> null
|
4 -> null

这么put/get性能就从O(1)变成了O(N),CPU负载呈直线上升,形成了拓宽版DDOS的功效,这种措施就是叫做hash攻击。在Java8挨经过应用TreeMap,提升了处理性能,可以得水平的防御Hash攻击。

3. 扩容

苟当表中之75%早就为占据,即视为要扩容了

(threshold = capacity * load factor ) < size 

她最主要有些许独步骤:

1. 容量加倍

错误移1各项,就是扩张至零星加倍,用个运算取代了乘法运算

newCap = oldCap << 1;
newThr = oldThr << 1;

2. 遍历计算Hash

for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果发现当前有Bucket
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //如果这里没有碰撞
                    if (e.next == null)
                        //重新计算Hash,分配位置
                        newTab[e.hash & (newCap - 1)] = e;
                    //这个见下面的新特性介绍,如果是树,就填入树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果是链表,就保留顺序....目前就看懂这点
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }

经过可望扩容需要遍历并重新赋值,成本大高,所以选择一个吓的开始容量非常主要。

安升级性能?

  1. 缓解扩容损失:如果掌握大致需要的容量,把开容量设置好为化解扩容损失;
    遵自己现在发出1000单数据,需要 1000/0.75 = 1333 只坑位,又 1024 <
    1333 < 2048,所以极好应用2048看成开容量。

  2. 釜底抽薪碰撞损失:使用便捷的HashCode与loadFactor,这个…由于JDK8的胜性能出现,这儿问题呢非老了。

  3. 解决数据结构选择的荒唐:在巨型的多少及寻找中考虑采用别的结构以TreeMap,这个就是是文化积累了。一般需要key排序时,建议以TreeMap,本文暂未讨论;

HashMap与HashTable的要区别

以许多之Java基础题上且早已说过了,他们之最主要分其实就是是Table全局加了线程同步保障

  • HashTable线程更加安全,代价就是是盖它们粗暴的增补加了合伙锁,所以会发性能损失。
  • 骨子里生更好之concurrentHashMap可以取代HashTable,一个凡是方法级,一个凡是Class级

JDK8中HashMap的初特点

一旦有桶中之链表记录了大之说话(当前凡TREEIFY_THRESHOLD =
8),就见面管这个链动态变成红黑二立交树,使查询最差复杂度由O(N)变成了O(logN)。

//e 为临时变量,p为当前的链
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

JDK8在其余地方也产生升迁,更多之得拘留这里。

HashMap的装箱空间效率

以笔试题中,一般“内存限制”是不考虑装箱的,而于切实可行中HashMap空间效率的不及,你倒是未自然知道。

随定义了一个 HashMap<Long,Long>

1. Long的装箱

当靶头着,加入额外的指针8Bype,加入8Bype的MarkWord(hashcode与锁信息),这里就是16Byte

也就是说,long在装箱后,效率为 8/24 = 1/3

2. Map.Entry的装箱

字段空间: hash(4) + padding(4) + next(8) =
16Byte,这里的padding是字节对同步

对象头: 16Byte,指针+MarkWord

也就是说,维护一个Entry需要32Byte之长空

static class Node<K,V> implements Map.Entry<K,V>
{    
    final int hash;    
    final K key;    
    V value;    
    Node<K,V> next;
}

3. 总效率

8/(24 + 32) = 1/7

算算结果可能发距离,本文主要在强调装箱过程导致的损失

在Android中使用SparseArray代替HashMap

法定推荐用SparseArray([spɑ:s][ə’reɪ],稀疏的数组)或者LongSparseArray代替HashMap,目前国内类似涉及的可比少,容我事先贴贴平段落

Note that this container keeps its mappings in an array data
structure, using a binary search to find keys. The implementation is
not intended to be appropriate for data structures that may contain
large numbers of items. It is generally slower than a traditional
HashMap, since lookups require a binary search and adds and removes
require inserting and deleting entries in the array.

For containers holding up to hundreds of items, the performance
difference is not significant, less than 50%.
To help with performance, the container includes an optimization when
removing keys: instead of compacting its array immediately, it leaves
the removed entry marked as deleted. The entry can then be re-used for
the same key, or compacted later in a single garbage collection step
of all removed entries. This garbage collection will need to be
performed at any time the array needs to be grown or the the map size
or entry values are retrieved.

总的来说就是:

  • SparseArray使用基本类型(Primitive)中之int作为Key,不欲Pair<K,V>或者Entry<K,V>这样的卷入类,节约了内存;
  • SpareAraay维护的是一个排序好之屡屡组,使用二划分查找数据,即O(log(N)),每次插入数据都设进行排序,同样耗时O(N);而HashMap使用hashCode来加盟/查找/删除数据,即O(N/buckets_size);
  • 由此看来,就是SparseArray针对Android嵌入式设备开展了优化,牺牲了轻微的年月性能,换取了重新甚之内存优化;同时她还有别的优化,比如对勾操作做了优化;
  • 假设您的数非常少(实际上为是如此),那么用SpareArray也是是的;

当笔试中的动

1. 查重与分组问题

某个商店正在举行一个寻找走去儿童之公益类,现在发一个函数,可以输入两个图片,并回到这个娃娃是否还。请您计划一个系,帮助她们搜寻孩子。

  1. 网友可以以上污染一模一样批图片
  2. 网会管拥有图片分类并由为同一组
  3. 网友及污染图片后,网页要快返回该照片四处的组。

A:假设你本产生一个机器,请写有你的数据结构与拍卖流程,设计之笔触。
B:如果您闹差不多台机械,如果缩短请求的日?

A:我们好管其说为简单个组成部分,一个是数据结构一个凡是达到传流程。

(1).
对于数据结构来说,一个凡对准小朋友信息进行打包,另一个是落实小朋友信息之全速查找。对于小孩信息包装类来说,除了入儿童的图,姓名,生日等中心信息外,特别要注意又写equals与hashCode,这个equals就是题材所说之比函数。对于查找的兑现的话,首先我们成立一个HashSet,用于存储儿童信息。网友齐传后,服务器通过对图像计算出特色Hash值,并查Hash表,如果HashCode相同,则归所于的组;如果未均等,就加盟hash表,伪代码如下。

List<Set<Child>> list;
list.forEach(set -> {
  if(!set.contain(child)){
     set.add(child);
  }
});

(2). 对于多图上传问题,有成熟之中件,比如MQ。

B问题:
此问题明显是一个事件处理与分发的流程。可以透过Hash后取余、随机,顺序,基于响应时间之权值等多种载重均衡路由政策。

TOP10的实现

摸引擎会通过日记文件将用户每次找使用的有所寻串都记录下来,每个查询串的长短也1-255字节。假设目前生一千万单记录(这些查询串的重复度比较大,虽然总数是1千万,但要除去重复后,不超过3百万独。一个查询串的重复度越强,说明查询其的用户更加多,也不怕是越来越吃香。),请而统计最红的10独查询串,要求下的内存不能够超过1G。

本条问题与齐独问题类似,我们挑选采取HashMap,key为查询值,val为计数,内存以呢
3 * 256 M == 768M < 1G,然后我们不住的put就好了,伪代码

HashMap<String, Integer> map = new HashMap<String,Integer>();
//如果内存再多点的话,我们就可以把初始化容量凑个1024的整数,减少扩容损失。

while(fileLog.hasNext()){
    String query = fileLog.next();
    map.put(query, map.get(query) + 1);
}

随之用堆排序遍历即可,堆的高低也10,复杂度为10xO(LogN)。

综上, 总复杂度为O(10^7) +10 * O(Log(3×10^6));

额外还有同种,就是采取Redis来实现TopN,即Sorted Sets,可以参照《Redis的筹划和落实》,里面也出口了Hash相关,不过大凡用C写的。

还有同种植是运LinkedHashMap<T,Integer>作为统计工具,内部就实现了渐进式排序,最后计算KeySet.subList(0,10)即可。

利用WeakHashMap作为缓冲

以动态代理、Spring依赖、NoSQL等耗查询时操作着,为了促成复用,使用了HashMap实现缓存,下面的一个例是Picasso的Transformation操作

public final class PaletteTransformation implements Transformation {
    private static final PaletteTransformation INSTANCE = new PaletteTransformation();
    private static final Map<Bitmap, Palette> CACHE = new WeakHashMap<>();

    public static PaletteTransformation instance() {
        return INSTANCE;
    }

    public static Palette getPalette(Bitmap bitmap) {
        return CACHE.get(bitmap);
    }

    private PaletteTransformation() {
    }

    @Override
    public Bitmap transform(Bitmap source) {
        Palette palette = Palette.generate(source);
        CACHE.put(source, palette);
        return source;
    }

    @Override
    public String key() {
        return "PaletteTransformation";
    }
}

附录一:集合中元素的排序方式:

巧对比SparseArray与HashMap时,我恐惧各位绕进去了,这里再次谈下Java中聚集的排序方式

  • 准添加/删除的顺序,比如FIFO,FILO,常见的照Queue,Stack就是遵循此顺序实现之;

  • 随Hash表进行排序,比如HashMap的table中之因素是经过hash运算随机均匀排列的(至少理论及是),可以透过计算Key的Hash值快速搜索到Value

  • 仍自定义的排序,比如按照数字大小,拼音首配母排序,常见的有线性顺序表,二叉查找树,以及高度封装好之TreeMap,它们要贯彻Comaparable接口以开展进一步的自定义CompareTo操作。

附录二:hashCode, == ,equals, Comparable的区别?

  • == : 这个就算是内存地址的可比,从C语言开始我们便了解此了。

  • hashCode/equals:对于Object来说,hashCode就是地方之取样运算,而equals就是判地址是否相同,是native方法,需要jvm实现;在骨子里利用中,特别是在集合(Set)中,特别是HashSet,为了预防插入的凡少单相同的价,我们又青睐内容达之对立统一而无是地点的对比,需要通过测算hashCode来判断是否equals,所以个别单主意要而重写,比如String。

  • Comparable:
    在集合需要排序(SortSet)的图景下,就待被目标实现Comparable接口,比如TreeMap。这个以Android开发中实际上需要手动写的情状并无多,毕竟包多,在ORM框架中貌似还拉你写好了。

Map在Android/Sever项目面临的行使

  1. Android中的Bundle与Parcelable,实际上即便是对准Map与Serializable的接口实现(当然底层已经是根据ASM的IPC了);
  2. 照时采取WeakReference做缓存,比如Retrofit等动态代理框架;
  3. Otto广播的底结构是HashMap<IBinder, ReceiverList>;
  4. 于Zookeeper等框架中,使用LinkedHashMap作为NamingService的休养存。
  5. 以Redis等框架中,作为重中之重的缓存结构。

后记

照王垠的话,JDK源码简直为丁无语,特别是if((n.next=p) != null)如此这般的代码频频出现,我个人非常不爱好(然并卵,现在羁押了晚已经会写来这种WTF的代码了)。这是本人首先蹩脚写分析如果不是写过程,希望生问题会提出,无论是文章排版还是技术上之题目都得以领取出来。

终极由只广告,我目前正在准备技术面试,所以有关Java所有的稿子有个小结,不妨体贴入微一下。

  • 扩展阅读:
    Redis的渐进式ReHash实现

Reference

  1. http://bigocheatsheet.com/
  2. https://github.com/android-cn/android-discuss
  3. http://www.ibm.com/developerworks/cn/java/j-jtp08223/
  4. http://www.jianshu.com/p/9a48bcbdfece
  5. http://www.jianshu.com/p/4e13fcdf9ab5
  6. http://blog.csdn.net/zimo2013/article/details/39692245
  7. http://coderbee.net/index.php/java/20131018/519
  8. http://www.guokr.com/blog/747926/
  9. http://blog.csdn.net/v\_JULY\_v/article/details/6256463
网站地图xml地图