hashmap

Question

有一个需求，需要实现对字符串的计数，然后存入数据库，不过字符串的种类有点多，0到百万级，请问如何实现？如果用默认大小的hashmap的话，不断的重构效率太低了，有什么好的解决办法？

Answer 1

以下几种方法仅供参考
1. 直接访问数据库，有则加1，没有则为1
2. 使用HashMap作为缓存(如存一万条，满了则把使用频率最低的移除并更新数据库)＋数据库查询
3. 使用文件对字符串排序，再统计存入数据库
4. 综合上面的方法一起使用.

Answer 2

建议把字符串分段。比如每8192个字节，遍历一遍，放到一个初始大小即为512的HashMap中计数（也可以初始大小1024，甚至256，就看你的样本如何了）。8k算完后，放到数据库中，然后new 一个新的HashMap，继续下一个8k。

Answer 3

  有以下几点可参考：
     1.可以采用缓存技术实现
     2.自定义一个类继承HashMap,进行一些处理，适合自己使用

Answer 4

仅仅是存储后拿HashMap来计数吗，默认大小太小就弄大点不好了吗

Answer 5

这么多数据当然放数据库，内存对象可以做个数据库的cache.

Answer 6

可能不太合适，我希望计数完成后统一更新数据库。或是我不太理解？
需求是这样的，一个文件，存储了很多个字符串，字符串的范围是知道的(0 - 100万都有可能出现0到若干次)，现在需要对每个字符串出现的次数进行计数，然后存入导数据库中。考虑过用两个arraylist，一个放字符串，一个放出现的次数。

Answer 7

最好都在数据库范围内处理
如果只是想计数的话，使用bitSet试试

Answer 8

举个例子，你现在统计的是《三国演义》。每次统计一回（我上面说的8K）统计这一回出现的字及其次数，假设第一回只有这样两行。
宴桃园豪杰三结义 斩黄巾英雄首立功
话说天下大势，分久必合，合久必分。那么这个map就是
宴1 桃1 园1 豪1 杰1 三1 结1 义1 斩1 黄1 巾1 英1 雄1 首1 立1 功1 话1 说 1 天1 下1 大1 势1 分 2 久2 必2 合2然后把这个map更新到数据库。每个字都先判断数据库是否存在，不存在就是insert存在就是update n=n+x第二回合
张1 翼1 德1 怒1 鞭1 督1 邮1 何1 国1 舅1 谋1 诛1 宦1 竖1
把这个全新map（区别于上一回合的map）更新到数据库。一样是区分insert/update一次性更新的话，map的大小可能很大。这样做的好处是，减少了Map总的大小，通常相近段落，出现的字词重复较多。不过，如果内存足够大的话，应该不是问题，因为中文常用字的个数顶多5000个。而每个字都更新数据库的话，开销也太大。

Answer 9

不知道听懂了没有。你前面说的2个arraylist，拜托你放弃。假如我统计到第99999个字的时候，是个“好”字，我怎么知道好的下标？不还得用map，难道你遍历一遍第一个list？？？？？？？！！！！！！

Answer 10

嗯，你的意思我大概明白了。
如果存入list的时候做一些处理，采用二分搜索得到下标，是否可行？如果在数据库查询的实现不也是采用的二分搜索的思想么？

Answer 11

拜托！！！别说二分查找，就是“八分”也没HashMap速度快。首先，HashMap的查询速度“几乎”和Map.size无关，也就是说，size=100的时候和size=100000的时候，get("X")的速度是一样的。但是二分法显然是和size有关。其次，你的list不是静态的，而是不停增长的。binarysearch要求有序。莫不是你插一个新的字，就排序一次？而且是arraylist，估计1000个字，你的时间是map的10万倍已经阿弥陀佛了

Answer 12

你这种需求场景会用到map的遍历，map的size就会影响到性能了

Answer 13

size一直都会影响性能，使用get方法的时候获取index是与size有关的。

Answer 14

在get方法时和size没有关系，因为HashMap只是利用table.length计算了一下这个元素在数组的哪个位置(bucketIndex)而已
int i = indexFor(hash, table.length);这样就得到了所在位置，然后HashMap再遍历这个位置上的链表判断。这个与size也没有关系，与factor有关（当然，如果你的key元素的hashCode写得很烂，导致大量key计算的位置都相同则会有关）

Answer 15

Hash算法的复杂度是O(1),二分法是O(log2 N).

Answer 16

HashMap的实现对于普通操作(get,put)都是常数时间级的，意味着不因size而变
这个结论是基于这样的前提：哈希函数以合适的方式散布map元素于map的buckets中public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = 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.equals(k)))
                return e.value;
        }
        return null;
    }这个问题就可以归到根据index取array元素 性能是不是受array.length所限

Answer 17

建议你在看下
indexFor(hash, table.length)方法，其实取是很快的，关键是你不能做那么大的map,占用内存太大

Answer 18

看indexFor干吗？内存只要够用又有何不可？不够的话就有上面提到的办法了～