1hash table部分

HashSet内部维护一个HashMap对象。分析HashMap源码：

                                                           

                                     final Entry<K,V> getEntry(Object key) {

                                                    if (size == 0) {

                                                             return null;

                                                    }

                                                    int hash = (key == null) ? 0 : hash(key);

                                                   for (Entry<K,V> e = table[indexFor(hash, table.length)];

                                                   e != null;

                                                   e = e.next) {

                                                       Object k;

                                                    if (e.hash == hash &&

                                                                  ((k = e.key) == key || (key != null && key.equals(k))))

                                                       return e;

                                                   }

                                                  return null;

                                     }

HashMap在查找一个key的对象内容时，通过将Key哈希，，然后比较列表中对象元素的hash值与key的hash是否相等，以及列表中的对像与key是否相等或者equals。

HashMap是线程不安全的，并且当Hash冲突时采用的方法是chaining(链表的方式解决)。

应用HashTable例子：

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

                                           

                        public RandomListNode copyRandomList(RandomListNode head) {

                                                  if(head==null)return null;

                                                 RandomListNode oldHead=head;

                                                 HashMap<RandomListNode,RandomListNode> map=new HashMap<>();

                                                 RandomListNode node=new RandomListNode(head.label);

                                                 RandomListNode res=node;

                                                 map.put(head,node);

                                                 while(head.next!=null)

                                                 {

                                                      node.next=new RandomListNode(head.next.label);

                                                      map.put(head.next,node.next);

                                                      head=head.next;

                                                      node=node.next;

                                                 }

                                                 head=oldHead;

                                                 node=res;

                                                 while(head!=null)

                                                {

                                                 node.random=map.get(head.random);

                                                 head=head.next;

                                                 node=node.next;

                                                }

                                               return res;

                               }