What is replacement of Sparse Array to be able to add same keys in this case?

Question

I write the application for android. I have several words(~50000) and I have to type any one word which begins from specified letter and remove the word. I store all words in Sparse Array and read words from file in it.

sparseArray = new SparseArray<String>();            
String str = "";
char c;
while ((str = stream.readLine()) != null) {
    c = str.charAt(0);
    sparseArray.put(c, str);
}

where key - first letter in word, value - a word.

When I receive a letter I select any word with same first letter

char receivedLetter;
...
String word = sparseArray.get(receivedLetter);
sparseArray.removeAt(sparseArray.indexOfValue(word));
Log.d("myLogs", "word: " + word);

But Sparse Array stores only 26 elements, because words with the same first letter(same key) are overwrited and remain only one last word. HashMap also don't decide the problem. What should I use to solve this problem?

Answer 1

There are several ways to do this. For example, without need to remove elements, you can use a sorted navigable collection such as a TreeSet.

TreeSet<String> words = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
words.add("hello");
words.add("beta");
words.add("beat");
words.add("couch");
words.add("alpha");
words.add("Bad");

Now you can do

NavigableSet<String> bWords = words.subSet("b", true, "c", false);
System.out.println(bWords); // prints [Bad, beat, beta]

And you're given the subset of words that are >= b && < c. You can then do

String removedWord = bWords.pollFirst(); // Bad
System.out.println(bWords); // prints [beat, beta]
// sub-sets affect their origin, they are "views on the original collection"
System.out.println(words); // prints [alpha, beat, beta, couch, hello]

And you've effectively removed a word with "b". A TreeSet has the advantage that you can navigate and search your data in many ways.

Based on a char the magic line of code to remove an element is

String removed = words.subSet(Character.toString(receivedLetter), true,
            Character.toString((char) (receivedLetter + 1)), false)
        .pollFirst();

The other alternative is a collection of collections. Like a SparseArray<List<String>>() for example

SparseArray<List<String>> sparseArray = new SparseArray<List<String>>();
String str;
while ((str = stream.readLine()) != null) {
    char c = str.charAt(0);
    // get or create list stored at letter c
    List<String> list = sparseArray.get(c);
    if (list == null) {
        list = new ArrayList<String>();
        sparseArray.put(c, list);
    }
    // add word to list
    list.add(str);
}

To remove, you get the list, if it's not null remove an element from it.

    char receivedLetter;
    List<String> words = sparseArray.get(receivedLetter);
    if (words != null && !words.isEmpty())
        words.remove(words.size() - 1);