7

So I need to have a some sort of multiset of characters, where adding a duplicate character increases the cardinality by 1, and the multiplicity of characters should not drastically increase the memory that the object takes up.

This will be implemented with some sort of map where characters are keys, that hold a value representing the number of that character is represented in the set.

However, I'm struggling to figure out which collection would be best for this (I was looking at hashmap) and how to declare this data type. I was doing something like this

Map m = new HashMap(char, int);

But the above is an incorrect declaration, and I'm not sure how to exactly approach this.

2
  • If you can use third-party libraries, Guava's Multiset might be more appropriate than a straight-up Map. Nov 28, 2012 at 0:15
  • @LouisWasserman I was describing it as multiset to describe the client view we need to appropriately implement. However we can only use the standard java libraries and api.
    – Aerlusch
    Nov 28, 2012 at 0:17

5 Answers 5

10

Try this declaration:

Map<Character, Integer> m = new HashMap<Character, Integer>();

You can then add characters as such:

char c = //...;
if (m.containsKey(c))
    m.put(c, m.get(c) + 1);
else
    m.put(c, 1);
1
  • 2
    Very helpful. Sometimes it's just hard reading through the api. Much appreciated.
    – Aerlusch
    Nov 28, 2012 at 0:13
3

I would implement it using int[] (for ASCII) or int[][] for unicode. Given the memory footprint of storing boxed integers in a hash map with all the hashing conflicts introduced by using numbers, and characters are nothing but numbers, as keys.

public class CharacterBag {

    private int[][] data = new int[255][];

    public void add(char ch) {
        int[] bin = data[ch >> 8];
        if (bin == null) bin = data[ch >> 8] = new int[255];
        bin[ch & 0xFF]++;
    }

    public int frequency(char ch) {
        int[] bin = data[ch >> 8];
        if (bin == null) return 0;
        return bin[ch & 0xFF];
    }

}

This starts with a memory footprint of zero, and adds 2K for each unicode page. Typically text uses characters from one or two unicode pages.

In comparison using HashMap will have the whole overhead of storing boxed primitives in a list of linked lists. For each character there will an object of the Entry class with two pointers pointing to a boxed key and a linked list object with all its fields and which holds an object of class Node with a forward and a backward pointer and which has a pointer to the boxed integer … shall I go on? ;)

3
  • Seeing how much attention previous answers got over this one, you wonder why java programmers get a bad rep, this answer should be at the top
    – niken
    Jun 17, 2014 at 21:15
  • For those of us new to binary shifting and masking... how would you iterate over the CharacterBag once you've filled it to get all characters w/cnt > 0?
    – Robert
    Jul 12, 2019 at 23:31
  • I think I got it...(char c = (char)((i << 8)+ii);) is the gist of it in my nested for loops over (data)
    – Robert
    Jul 12, 2019 at 23:58
2
Map<Character, Integer> charCount = new HashMap<Character, Integer>();

public void addCharacter(char c) {
    Integer value = charCount.get(c);
    if (value == null) {
        charCount.put(c, 1);
    } else {
        charCount.put(c, value + 1);
    }
}
0

Java collections does not allow you to create a collection of primitive types, rather you should use their respective wrapper class (eg The wrapper class for int is Integer).

Map<Character,Integer> hashMap = new HashMap<Character,Integer>();

This how you declare a map. for more examples and explanation please look here

0

Best way according to me is to use the constructor:

Map<Key, Value> orgMap = new HashMap<Key, Value>();
Map<Key, Value> copyMap;
copyMap= new HashMap<Key, Value>(map);

Keep it simple.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.