大数据计数原理 1+0=1 这你都不会算（一）

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\&\#39\;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的开销，只能说是吃内存大户。

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

;