浅谈HashSet和HashCode

一.HashSet

Kotlin中 ==HashSet==是一个集合类，它扩展了==AbstractMutableSet==类并实现了==Set==接口。 ==HashSet==类使用散列机制存储元素。 它支持读写功能。 ==但它不支持重复值==，也不保证元素的顺序。

HashSet申明：

open class HashSet<E> : AbstractMutableSet<E> (source)

HashSet构造函数：

构造函数	描述
HashSet()	构造一个空的HashSet实例
HashSet(initialCapacity:Int,loadFactor:Float = 0f)	构造一个指定容量的HashSet实例
HashSet(elements: Collection<E>)	使用指定的集合元素构造HashSet实例

HashSet成员函数

函数	描述
open fun add(element: E): Boolean	如果此 set 中尚未包含指定元素，则添加指定元素；如果此 set 已包含该元素，则该调用不更改 set 并返回 false。
open operator fun contains(element: E): Boolean	它检查当前集合中是否存在指定的元素。
open fun isEmpty(): Boolean	它检查当前集合是否为空(不包含任何元素)。 如果找到的集合为空则返回true，否则返回false。
open fun iterator():MutableIterator<E>	它返回当前对象元素的迭代器。
open fun remove(element: E): Boolean	如果当前集合中存在，它将删除提及元素。 如果删除成功则返回true，则返回false。
open fun clear()	它会删除此集合中的所有元素。

HashSet属性

函数	描述
open val size: In	此属性用于返回HashSet集合的大小。

点进代码可以发现Kotlin中的HashSet其实就是借用了java.util.HashSet

public actual typealias HashSet<E> = java.util.HashSet<E>

一道关于HashSet的Java笔试题：
对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。
给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于500。
测试样例：
"eredfdad",8
返回：e
代码：

public class FirstReport {
    public static char findFirstRepeat(String A, int n) {
        char[] a=A.toCharArray();
        HashSet hashSet = new HashSet();
        for (int i = 0; i < n; i++) {
            if(!hashSet.add(a[i])){   //如果加入失败 返回false
                return a[i];
                }
        }
        return 0;
    }

    public static void main(String... args) {
        System.out.println(findFirstRepeat("eredfdad",8));
    }
}

输出：e 说明了集合中只能够存放唯一的对象，也就是相同的对象只会存放一个。

二.hashCode和equals()方法

哈希表这个数据结构想必大多数人都不陌生，而且在很多地方都会利用到hash表来提高查找效率。在Java的Object类中有一个方法:

public native int hashCode();

关于HashCode的官方文档定义:

hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点，
例如，java.util.Hashtable 提供的哈希表。hashCode 的常规协定是： 
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。 
如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 

对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。
　
　　为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）
也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但假如有很多条数据的话，如果采用equals方法去逐一比较，效率必然是一个问题。
此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列它的地址，所以这里存在一个冲突解决的问题，学过数据结构的应该想到，解决冲突的方法常用的有：双散列函数探查法和平方探测法等，这样实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。

 假如内存中有这样的位置：
 0 1 2 3 4 5 6 7 
 将带有ID的字段的类存放进内存 我有个类，类里有字段叫做id,要把它放进这个内存中之 如果你不 
 用hashcode，而是乱放的话，那么当查找时就需要到这八个位置里挨个去找，或者用一些查
 找的算法。但如果用hashcode那就会使效率提高很多。
 假设定义hashcode=ID%8,比如有一个ID为9，9除8余1，把此类放在1的位置，查找该类时，就通过
 该类的ID%8来获取存放的地址。
 但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和
 17除以8的余数都是1，存放的时候通过解决冲突的方法存放，但是依然会有不同的ID的类被放到一起，
 这时候查找的时候就需要 equals来确定此对象是否是你想要的对象。所以hashcode()和equals()需要
 一起重写。你需要先通过hashcode找到对象，再用equals判断对象。

来看一段代码:

class Person(var age:Int,var name:String){
    override fun hashCode(): Int {
        return age%7
    }

}

fun main() {

    val persons = HashSet<Person>()
    val a=Person(20,"CZ")
    val b=Person(20,"CZ")
    persons.add(a)
    persons.add(b)
    println(a.hashCode()==b.hashCode())
    println(persons.size)
    println(persons)
}

输出：
true
2
[com.czwl.kotlin.types.eg.Person@6, com.czwl.kotlin.types.eg.Person@6]

此时没有复写equals,只是重写了hashcode方法，于是会调默认的方法，将a,b 放入HashSet中，但HashSet只能够存放唯一的对象，也就是相同（适用于equals方法）的对象只会存放一个，但是这里实际上是2个相同的都被放到了HashSet中，这样HashSet就失去了他本身的意义了。
此时再重写equals方法：

class Person(var age:Int,var name:String){
    override fun hashCode(): Int {
        return age%7
    }
    override fun equals(other: Any?): Boolean {
        val other=(other as?Person)?:return false //判断是否为Person 
        //是的话强转为Person
        //不是返回false
        return other.age==age&&other.name==name
    }
}

fun main() {

    val persons = HashSet<Person>()
    val a=Person(18,"CZ")
    val b=Person(18,"CZ")
    persons.add(a)
    persons.add(b)
    println(a.hashCode()==b.hashCode())
    println(persons.size)
    println(persons)
}

输出：
true
1
[com.czwl.kotlin.types.eg.Person@6]

现在两个对象就完全相等了，HashSet中也只存放了一份对象。