hash表与java集合框架

1. 对象被new出来后，会通过哈希函数Hash(key)建立关键字key与存储地址Addr的关系，Addr = Hash(Key)，这个Addr又称HashCode。即：每个对象有唯一的HashCode。

　　- 另外：底层对对象进行hash时因为hash表长度有限所以存储可能会有冲突，为了解决冲突而在顺序表的某个存储地址上加了一个链表。hashTable存储结构：

2. java中 == 和equals() 的区别就在于此：==比较的是两个对象是否是同一个对象，即：a和b是否是同一个hashcode；而equals()只是比较a和b的值是否相等，并不比较a和b的hashcode是否相等。

　　- 另外：java中的set里的对象是不重复的，这个“不重复”也是根据hashcode来判断是否重复。

3. java中的集合框架有collection、map。

　　a. collection= list+set = ArrayList + LinkedList + HashSet + LinkedHashSet + TreeSet 。

　　b. map = HashMap + LinkedHashMap + TreeMap。

　　- 顾名思义：ArrayList底层使用数组实现，因此就有底层顺序表的优点和缺点

　　　　　　　  LinkedList、LinkedHashSet、LinkedHashMap底层用双链表实现，因此也是有序的，也有底层双链表的优点和缺点

　　　　　　　  HashSet完全使用HashTable实现，LinkedHashSet/LinkedHashMap比前者多了一个双链表用来记录前后结点顺序

　　　　　　　  TreeSet、TreeMap底层用红黑树实现，可进行排序(需要对象实现Comparable接口，或者调用TreeSet/TreeMap的有参构造器：public TreeSet(Comparator<? super E> comparator))

　　　　　　　   Map和Set的底层实现基本一致，只是Map需要多存储一个value。

　　c. Map转Set：Set<Map.Entry<Object,Object>> entries= map.entrySet();

　　d. java中HashMap的时间复杂度是O(1)，因为HashMap底层是用顺序表(+链表)实现的，有随机读取的特性。