请教Hashmap 数量问题

各位大牛，我这里有一个小问题请教：刷题常常需要用到hashmap作为字典去存char出现的数目，我们都知道可以用一个int array去代替hashmap，每一个index对应一个unique char，我的问题是这个array多长比较合适？有人说128，因为ascii 表里有128个；有人说256，也就是unicode的数目。什么情况用unicode（比如只有english characters？）什么情况用unicode，用unicode的话应该用多长的array呢？
感谢大家！

要具体看你需要建立的"词典"的大小。
比如说题目里面规定了只有小写字母，那么26的大小就足够了：

1. int[] freq = new int[26];

复制代码

。可能有点啰嗦的是用

1. ch - 'a'

复制代码

来定位，比如这句:

1. ++freq[ch - 'a'];

复制代码

。与之对应的，还原成字符串的时候:

1. freq[idx] + 'a'

复制代码

.
类似的，如果题目里面规定了只有大写字母情况，也可以用这样的办法解决。

但是，有时候题目里面有大写字母，也有小写字母，甚至还有特殊字符，但没有超出ASCII码的范畴，往往定义一个128大小的数组:

1. int[] freq = new int[128];

复制代码

。但是就不需要+/- 'a'来进行定位了，直接

1. freq[idx]

复制代码

就好。

有时候图省事，不想+/-'a'，我会把第一种写成第二种。

基于数组的自加减会比基于Map自加减方便不少。freq[idx]的自加减操作是O(1),整个过一遍也不过是O(26/128) ~ O(1)。
但是如果"keys"太稀疏，也建议使用HashMap来建立"词典"。

没有必要纠结128还是256，不差那么几个byte。要真想知道到底几个，网上找一张ASCII表看看就知道了。
另外你对Unicode的理解有偏差，Unicode光基础字符就有0x0000~0xFFFF https://zh.wikipedia.org/wiki/Un ... 2%E6%98%A0%E5%B0%84

取决于数据的key有多少个吧,而且只有key比较少的时候用array代替hashmap才有优势吧,不然array稀疏度太高了,用hash function可以使key尽量均匀分布, 而且一旦hashmap过饱和了,也会自动扩容的

witcher_ciri 发表于 2020/06/11 10:55:50
取决于数据的key有多少个吧,而且只有key比较少的时候用array代替hashmap才有优势吧,不然array稀疏度太...

谢谢。如果确定key就是char，怎么能知道用128的ascii就够了而不需要unicode？

火锅烧烤麻辣烫 发表于 2020-6-10 22:39
谢谢。如果确定key就是char，怎么能知道用128的ascii就够了而不需要unicode？

取决于char这个数据类型占多少个bit吧,像c里面,每个char是8bit的话就是128种可能呗.Unicode每个字符是由多个byte组成的,不像一个char就是一个byte

什么情况用？刷题的时候用。工作中这么用十有八九会崩。

绝大多数情况遇到的char也就是word char(i.e., [a-z_A-Z0-9])和white space (\s)还有一切punctuation，很少涉及到unicode里面其他的字符的，最常见的就是统计26个字母，不放心就用256个，反正多出来也浪费不了多少空间但是可以防止数组越界

另外上面有人提到不同语言char类型的大小不一样，C语言就是一个byte（对应ascii的128个字符），java的char是2个byte，因为用的某种unicode

原来的帖子不能修改了，补充区域也写不了多少字。我干脆再回一贴吧，顺便求大米。
int[] freq = new int[26/128] 这样建立"字典"，会在String - 去重、寻找Word Pattern(比如KMP算法)类问题里广泛使用。除了可以记住各个字母的frequency、实现Character <-> Integer的快速转换之外，还可以在使用滑动窗口寻找Word Pattern的时候，快速标记一个Word已经全部读入或者读出(具体可以参考KMP算法)。
使用HashMap也有其优点，比如需要记录的不仅仅是frequency，而是一些List(s)或者Set(s)： Map<Integer, Set<Integer>>..., Map<Integer, List<Character>>..., etc.相对来说，适用面更广泛一些。
需要注意的是，accesses by keys in a HashMap不是严格意义上的O(1),而是amortized(1)。这点也可以在LC上直接得到印证。同样的"字典"，HashMap会比array(int[])的耗时多不少。如果数据量不大，差异更是夸张。