Wepay OA

magicalcan 发表于 2015-9-13 22:28
lz能不能私信我code，我刚做了OA，md最后一个case总是过不了，不知道为什么，最后时间到了，我想看看哪有问 ...

你的hash function怎么写的啊，我猜测是hash function有问题吧，我室友也是这个问题，我看他代码结果发现他的hash function是在key是字符串的时候用字符串的长度%size, 然后导致长度相同的key都放在一个bucket里了，然后LTE了, 正确地做法是hash(key)%size.

yawnzh 发表于 2015-9-15 05:14
你的hash function怎么写的啊，我猜测是hash function有问题吧，我室友也是这个问题，我看他代码结果发现 ...

我是有一个Entry<K, V>类。
然后index = key.hashCode()%size;
key 就是put或者get的参数 key，size就是初始constructor设定的一个数；
然后用index取arraylist<LinkedList<Entry>>里的某一个linkedlist。然后for(Entry e: linkedlist)找有没有e.key.equals(key)的

yawnzh 发表于 2015-9-15 05:14
你的hash function怎么写的啊，我猜测是hash function有问题吧，我室友也是这个问题，我看他代码结果发现 ...

linkedlist 需要自己写么，还是直接用list

xytan123 发表于 2015-9-15 09:11
linkedlist 需要自己写么，还是直接用list

不用自己写

我也是第二个test case一直没过，估计挂了。

同样index = key.hashCode()%size; 还有什么地方可能出问题吗？

niubi 发表于 2015-10-4 06:15
我也是第二个test case一直没过，估计挂了。

同样index = key.hashCode()%size; 还有什么地方可能出问题 ...

index = key.hashCode()%size这样写不对吗？

1. public class MyHashMap<K, V> {
   
2.    
   
3.     class Entry<K, V> {
   
4.         K key;
   
5.         V value;
   
6.         Entry (K key, V value) {
   
7.             this.key = key;
   
8.             this.value = value;
   
9.         }
   
10.     }
    
11. 
    
12.     private int capacity = 16;
    
13.     private List<LinkedList<Entry<K, V>>> buckets;
    
14. 
    
15.     public MyHashMap() {
    
16.         buckets = new ArrayList<>();
    
17.         for (int i = 0; i < capacity; ++i) {
    
18.             buckets.add(i, null);
    
19.         }
    
20.     }
    
21. 
    
22.     public void put (K key, V value) {
    
23.         if (key == null) {
    
24.             throw new NullPointerException("Key cannot be null!");
    
25.         }
    
26.         int index = key.hashCode() % capacity;
    
27.         if (buckets.get(index) == null) {
    
28.             buckets.set(index, new LinkedList<Entry<K, V>>());
    
29.         }
    
30.         LinkedList<Entry<K, V>> bucket = buckets.get(index);
    
31.         Iterator<Entry<K, V>> iterator = bucket.iterator();
    
32.         while (iterator.hasNext()) {
    
33.             Entry<K, V> entry = iterator.next();
    
34.             //key already exists, value is updated
    
35.             if (entry.key.equals(key)) {
    
36.                 entry.value = value;
    
37.                 return;
    
38.             }
    
39.         }
    
40. 
    
41.         //key doesn't exist yet
    
42.         bucket.add(new Entry<>(key, value));
    
43. 
    
44.     }
    
45. 
    
46.     public V get (K key) {
    
47.         if (key == null) {
    
48.             throw new NullPointerException("key cannot be null!");
    
49.         }
    
50. 
    
51.         int index = key.hashCode() % capacity;
    
52.         if (buckets.get(index) == null) {
    
53.             return null;
    
54.         }
    
55.         LinkedList<Entry<K, V>> bucket = buckets.get(index);
    
56.         Iterator<Entry<K, V>> iterator = bucket.iterator();
    
57.         while (iterator.hasNext()) {
    
58.             Entry<K, V> entry = iterator.next();
    
59.             if (entry.key.equals(key)) {
    
60.                 return entry.value;
    
61.             }
    
62.         }
    
63.         return null;
    
64.     }
    
65. }
    

复制代码