leetcode 217. Contains Duplicat hash解法及相关hashmap与hashset问题

对于leetcode271题来说，当用hash的思路来解决时（当然有更快的方法，方法 一），发现用Set实现ok，用Map实现就会出现超时。
方法一：

public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int len=nums.length;for(int i=0;i1;i++)if(nums[i]==nums[i+1]) return true;return false;}

import java.util.Hashtable;
public class Solution {public boolean containsDuplicate(int[] nums) {Hashtable ht=new Hashtable();for(int i：nums){if(ht.contains(i))return true;ht.put(i);}return false;}
}

import java.util.HashSet;
public class Solution {public boolean containsDuplicate(int[] nums) {Set ht=new HashSet();for(int i：nums){if(ht.contains(i)return  true;ht.add(i);}return false;}
}

以上两程序，一个用Set，一个用Map。而HashSet的实现是建立在HashMap上的。具体到本程序中。add（）调用的是put（）

 private static final Object PRESENT = new Object();public boolean add(E e) {return map.put(e, PRESENT)==null;}

但是连个类中的contains（）实现原理却大为不同。HashTable中：

public synchronized boolean contains(Object value) {if (value == null) {throw new NullPointerException();}Entry tab[] = table;for (int i = tab.length ; i-- > 0 ;) {for (Entry e = tab[i] ; e != null ; e = e.next) {if (e.value.equals(value)) {return true;}}}return false;}

每次都要遍历table数组。
再看HashSet中的contains（）

public boolean contains(Object o) {return map.containsKey(o);}public boolean containsKey(Object key) {return getEntry(key) != null;}final Entry getEntry(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);for (Entry 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;}

直接通过索引找到table中的位置。而hashset的contains调用的是hashmap的containskey，所以此处调用hashmap然后调用containsKey同样可以通过。

由于put中都是用的索引直接定位，所以而已根据put的返回值来判断是否添加成功。
例如

HashMap map = new HashMap();for (int i : nums) {if (map.put(i, i) != null) return true;}return false;public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);for (Entry e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！