Question

HashSet类和hashCode()方法的小疑问！

HashSet类和hashCode()方法中，将一个对象放入集合中的时候，和“取模”有什么关系哈？简单说一下吧···

Answer 1

要了解这事情，就得理解HashSet（还有HashMap等等用hash值的类）的原理了。

HashSet是一个集合，集合的特点是里面不能有重复的元素，所以在往里加东西的时候，这个集合先得看看是否里面有这么一个元素了，这就牵涉到查找。其他类型的聚合，比方说一个ArrayList，你怎么知道某东西是不是已经在里面了？一般说来只有一个个找过去对比。可以想象如果元素很多的话这效率很低。所以要想办法优化，而用hash值就是这样一种优化法。

如果把聚合（Set,List之类的东西）看作是图书馆，必须“一个个找过去”的那种图书馆就是书随便堆成一堆的图书馆，每次有人来借书了，管理员听到名字，就去一本本地翻，运气不好得几乎找遍所有的书，才能找到要找的。

聪明的办法当然是先把书分成一些类别，每个类别做个书架，分门别类放好，这样有人来借书了，你先看看这书是归到哪类的，然后去那书架上一本本找。虽然还是一本本找，可是这次要找的范围就小多了。

hash值就是把对象归类的方法，虽然这个方法人类有点不好理解，但对电脑很容易，这就够了。hash值的特点是，对相同的对象，值总是相同的（一本书只能归在一类），不同的元素可能也有相同的hash（多本书可能归在同一类）。hash值的算法是很有讲究的，要能分类均匀，否则大多数书架上只一本书，几乎所有书都在某个书架上，那跟原来没有效率的做法也没区别。

还有一个问题是，hash值的取值范围很大，比如java中hashCode()返回的是一个int，真的针对每个hash值分一类的话，那就好像图书馆里只有几千本书，却要做多少亿亿个书架一样，实在没必要也不可能。所以要取模，把模作为分类，以便缩小分类的数目，比如以10为模，那么hash值是1，11，21，100001等等的原本不是一类的，都算是同类的东西了，但是原本hash值是11和12的，还是算不同类的东西。以10为模可以看作是做10个书架。

如果你看HashMap的源码的话，就会发现这个模也是会根据元素个数变的，就好比图书馆里如果只有几十本书，那做十个书架也差不多了，每个书架上平均几本，但是如果书的数目到成千上万了，那每个书架上平均几百上千本，就嫌多了点，于是我们把模数增大，比如100，那么hash值1和11就不是同类了，也就是原来同书架的书被放到不同书架上了，查询起来就快了。