0

I have 100 entries and I have to have to hash these into a hashtable of a limited size.

I know how to work with the first entry, ht.put(k,v) does the trick.

But as soon as I want to add another value to it, the old one gets overwritten. I don't want to do that, I want to append it in a linkedlist or arraylist.

Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>(211);

ht.put(1, 40);
ht.put (1, 60);

System.out.println(ht.get(1));
// output is 60

How to make it both 40 and 60?

Mayur Tolani
  • 1,458
  • 3
  • 17
  • 28

5 Answers5

2

You can have List as value type like:

Hashtable<Integer,List<Integer>> ht = new Hashtable<Integer,List<Integer>>(211);

And your put operation would look like:

public static void put(Hashtable<Integer,List<Integer>> ht, int key, int value) {
    List<Integer> list = ht.get(key);
    if (list == null) {
        list = new ArrayList<Integer>();
        ht.put(key, list);
    }
    list.add(value);
}

[UPDATE1] If you want you can make your one extension of Hashtable like:

public class MyHashtable extends Hashtable<Integer,List<Integer>> {
    public MyHashtable(...) {  // add params if needed
        super(...);
    }

    // with additional method:
    public static void putOne(int key, int value) {
        List<Integer> list = this.get(key);
        if (list == null) {
            list = new ArrayList<Integer>();
            this.put(key, list);
        }
        list.add(value);
    }
}
rsutormin
  • 1,629
  • 2
  • 17
  • 21
  • this means I am overriding the put method of the hashtable right? @rsutormin – Mayur Tolani Oct 30 '16 at 22:19
  • 1
    As of Java 8, you can do this in a single line: `hashTable.computeIfAbsent(key, k -> new ArrayList()).add(value);` In fact, [the documentation](https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function-) has an example of exactly this use case. – VGR Oct 30 '16 at 22:37
  • @MayurTolani: answered to you in [UPDATE1] in my main answer. – rsutormin Oct 30 '16 at 22:50
  • @VGR, this is handy! – rsutormin Oct 30 '16 at 23:00
1

You need linear probing http://www.sanfoundry.com/java-program-implement-hash-tables-linear-probing/

It's not possible to store more than one value in a cell of a hash table

When trying to map a new key to an already occupied cell this is called a collision.

There are a few algorithm schemes to try and work around collision, one is Linear probing - which finds the next most appropriate free space for the key to be stored

enem95
  • 34
  • 4
1

The data structure you are looking for is called Multi Map. By definition it has different interface than a map, because it allows multiple values associated with the same key.

There's no standard library implementation for this data structure yet. But you can find good ones in some open source libraries:

xiaofeng.li
  • 8,237
  • 2
  • 23
  • 30
0

You are using same key (1), which is not what you wanted, unless you wanted to add more values to the same key, in that case have hashtable of list of arrays HashMap<Integer,List<Integer>> integerArrayMap.

In Hashtable, the Key MUST be unique, as you are NOT using unique keys, the same value is being replaced. so try to put the values with different keys.

ht.put(1, 40);
ht.put (2, 60);

I suggest you to refer the Hashtable api here: https://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html

Ubaby
  • 37
  • 6
Vasu
  • 21,832
  • 11
  • 51
  • 67
0

Multimap (https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Multimap.html) should help if you are allowed to use it.

Alternatively, you could use Map<Integer, List<Integer>>.

Andy
  • 1,023
  • 1
  • 9
  • 17