专栏首页一名叫大蕉的程序员大数据计数原理1+0=1这你都不会算(一)No.47

大数据计数原理1+0=1这你都不会算(一)No.47

hello哈,大家是不是好久没见到我啦?我也是一直在摸索小伙伴们喜欢看到什么东西,不喜欢看什么东西,还请大家多多支持。为了表示感谢。小蕉在这给你们一鞠躬,二鞠躬,三。事不过三~

1+0=1你都不会谈什么大数据?

这篇呢,又是开坑之作,这是一个系列,主要会将大数据下的计数原理。说到计数,不知道大家会第一印象想到什么,我估计会是。。数手指。。没错,小蕉从小学开始就开始数手指,所有20以内的加减法很早就掌握了。研表究明,这估计也是我们现在使用十进制的原因,如果我们每个人每只手都有6只手指,那我们可能就用十二进制了。

好了不扯了,那用程序怎么计数呢?要去重那种。按照我拍脑袋设想呢,第一印象,嗯用HastSet准没错,但是HashSet占用的内存有多少你们知道吗?可以装下我一年的米饭。内存占用太大,所以就有了后面的B-tree,Bitmap,Bloom Filter,Linear Counting,LogLog Counting,Adaptive Counting,HyperLogLog Counting,HyperLogLog++ Counting。

如果现在你们一个都听不懂的话,那就对了,但那也木有关系,我会一个一个跟你们讲清楚哒。(如果我不断更的话,嗯)

那第一篇就开始讲HashSet是怎么进行计数的吧。首先我们看一下HashSet的底层结构是什么。

from HashSet

private transient HashMap<E,Object> map;
public HashSet() {
    map = new HashMap<E,Object>();
}

唔,咩你甘噶。想不到你是这样的HashSet,底层居然是一个私有的无法序列化的HashMap,黑人问号脸。计数嘛,我们就会想知道,集合中有没有存在过这个数字,那HashSet是怎么知道它自己的集合中有没有存在某个值的呢?

from HashSet

public boolean contains(Object o) {
    return map.containsKey(o);
}

oh,原来是直接调用了HashMap的containsKey这个方法,那HashMap又是怎么找的呢?

from HashMap

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

看不懂也没关系我讲给你听。首先算一下key的hash值,然后在自己的HashEntry的数组里面(其实就是一个元素都是链表的数组,哎呀好拗口),找到对应的HashEntry,找到之后呢,再根据链表一个一个找,如果发现key的hash值,引用,或者equals完全相等,嗯没错,那这个key就已经存在在HashSet中啦。这时候计数就不用+1了。

那如果一个值不存在呢?那就计数+1,顺便把自己放到集合里边嘛~怎么放呢?程序员有一句黑话叫,"don't bb,show me the code"。

from HashSet

private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

由此可见,也只是调用了HashMap的put方法,还特么把一个叫PRESENT的不知道什么鬼的静态的私有的无法修改的Object当成value值了。oh好像这样也可以理解,我们只是需要借助HashMap的key就知道重不重复了。至于HashMap是怎么put一个值得呢?

from HashMap

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

好这一堆基本都不用看,就看那个addEntry就够了,上面一大坨大概的意思就是,如果key已经存在了,那就覆盖原有的value值,然后就啥也不干,这不是我们本次的重点(modCount跟线程安全有关感兴趣同学自省度娘)。

from HashMap

  void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
               table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
               if (size++ >= threshold)
                   resize(2 * table.length);
 }

这一小段大概的意思呢,就是,把原来HashEntry的数组对应hash位置的值拿出来,然后把现在的值接到最前面去。然后非常关键的代码出现了。

size++

哇哇哇,size++,嗯,计数靠谱了,可以计数了。

from HashSet

public int size() {
    return map.size();
}

from HashMap

public int size() {
    return size;
}

嗯我们可以看到,就是直接把size返回了。

到这里我们已经说完了HashSet的计数原理啦。那么如果有N个值,这个HashSet需要多少空间呢?假设整个HashMap都放满了。

至少需要N*8+PRESENT,还要加上HashEntry的开销,只能说是吃内存大户。

下一次,我们继续聊聊,稍微不太那么占内存的计数方法。

本文分享自微信公众号 - 一名叫大蕉的程序员(DaBananaTalk),作者:大蕉

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 餐厅老板要累疯了No.2

    我是小蕉。 从前有座山,山里有座庙,庙里有个老和尚,阿不,有个餐厅的老板,在每天午餐之前,都要自己亲力亲为为各个小伙伴分配任务,大喊一声开饭啦,大家就屁...

    大蕉
  • 【侠客行】Lombok深度解析

    Lombok能以简单的注解形式来简化java代码,提高开发人员的开发效率。例如开发中经常需要写的javabean,都需要花时间去添加相应的getter/sett...

    大蕉
  • 元认知的一点点片言只语 No.87

    If not me , who ? If not now , when ? 最近逐渐发现,认知是一件很好玩很好玩的东西。它有时候能助你跃迁,有时候也能拖住你,...

    大蕉
  • 【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

    准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

    弗兰克的猫
  • Java集合中的HashMap类

             HashMap作为最常用集合之一,继承自AbstractMap。JDK8的HashMap实现与JDK7不同,新增了红黑树作为底层数据结构,结构...

    用户1148394
  • JDK7 与 JDK8 中 HashMap 的实现

    而这个Entry应该放在数组的哪一个位置上(这个位置通常称为位桶或者hash桶,即hash值相同的Entry会放在同一位置,用链表相连),是通过key的hash...

    剑影啸清寒
  • Java集合详解4:HashMap和HashTable

    HashMap也是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以key-value的形式存在。在HashMap中,key-val...

    Java技术江湖
  • Java集合详解4:一文读懂HashMap和HashTable的区别以及常见面试题

    《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。

    Java技术江湖
  • 算法与数据结构(2),Map

    睡了不到六个小时,被一个很奇葩又很奇怪的梦吓醒,以最快的速度穿好衣服,跑下楼去买了杯咖啡上来,文字没写多少,咖啡倒是一饮而尽。

    小鄧子
  • HashMap中add()方法的源码学习

    HashMap中实际是维护了一个Node数组,用来存储数据,下面看一下Node源码:

    会说话的丶猫

扫码关注云+社区

领取腾讯云代金券