现在需要一种压缩方法,把幂的连乘方案系统中得到的巨大整数压缩到可接收的数组范围中
对于英文词典,多大数组才合适呢?
如果重要50000个单词,可能会定义一个长度位50000的数组
但是实际情况中,往往需要更大的空间来存储这些单词。
因为我们不能保证单词会映射到每一个位置
比如两倍的大小:100000
如何压缩呢?
现在,就找一种方法,把0到超过700000000000000的范围,压缩到从0到100000
有一种简单的方法就是使用取余操作符,它的作用是的到一个数被另外一个数整除后的余数
取余操作的实现:
为了看到这个方法如何工作,我们先来看一个小点的数字范围压缩到一个小点的空间中
假设把0-199
的数字,比如使用largeNumber
代表,压缩到0到9
的数字,比如使用smallRange
代表
下标值的结果: index = largeNumber % smallRange
当一个数被10整除时,余数一定在0-9直接
比如13 % 10 = 3, 157 % 10 = 7;
当然,这中间还是会有重复,不过重复明显变小了,因为我们的数组是100000,二只有50000个单词
就好比,你在0-199中间选取5个数字,放置这个长度位10的数组中,也会重复,但是重复的概率非常小(后面会讲到真的发生重复了应该怎么解决)
认识上面的内容:相信你应该懂了哈希表的原理了,我们来看看几个概念:
- 哈希化: 将大数字转成数组范围内下标的过程,我们就称之为哈希化
- 哈希函数: 通常我们会将单词转成大数字,大数字在进行哈希化的代码实现放在一个函数中,这个函数我们称为哈希函数
- 哈希表:最终将数据插入到的这个数组,对整个结构的封装,我们就称之为是一个哈希表
但是,我们还有问题需要解决?
- 虽然,我们在一个100000的数组中,放50000个单词已经足够
- 但是通过哈希化后的下标值依然可能会重复,如何解决这种重复的问题呢?