alan_navarro's blog

Question for Java programmers
By alan_navarro, 11 years ago, In English

Hello Community. I have a question to all Java programmers. Given 10 000 000 random strings with the form "X-NN-XX" where X represents a english capital letter and N a number, count the number of differents strings and print this number.

I wrote a code which override the hashCode of a class Key, where returns the attribute (which is a representation of the string in 36-base) but the program never ends. I suppose my way to generate the 36-base int is not good.

Anyone can help me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

String has it's own hashCode(). Why do you need to override it?

About 36-base — yes, you shouldn't do that way. I would use polynomial hashes and 1e9 + 7 modulo.

UPD. I think, your problem is too many objects have the same hashes. You must use big prime modulo for hashes.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't override the hashCode() of String, i override the hashCode() of my class Key beacuse the String hashCode is more slow than just return the number in 36-base.

    public int hashCode() {

    return value;

    }

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by 36-base? And how do you get your %value%?

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you need hash? Just use simple array with structure like this — [Letter X][Number NN].

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Part of the task is do it with HashSet or TreeSet but it is a very good way to do.

    Thanks.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Key seems like a class that you've written yourself. Since you're overriding hashCode(), are you certain that your equals() also work correctly/overriden? If you didn't rewrite equals(), then even with the same hashcode the HashSet/HashMap is going to judge same Key different since the default equals() compares the object id (which is different for every object).

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As Jokser said, why not something like this? Datastructures from the standard library in Java should never be used unless needed (since they generally suck and force you into using the Integer class in a case like this which will waste both memory and time).

final boolean[] mark = new boolean[10*10*26*26*26];
int cnt = 0;
for(String s : input)
{
    //s = "x-pq-yz"
    final char[] c = s.toCharArray();
    final int x = c[0]-'A', p = c[2]-'0', q = c[3]-'0', y = c[5]-'A', z = c[6]-'A';
    final int idx = p*10*26*26*26 + q*26*26*26 + x*26*26 + y*26 + z;
    if(!mark[idx]){ ++cnt; mark[idx] = true; }
}

return cnt;
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, it's so much better implementation of the idea than mine. I use a array[26][10][10][26][26]. I have so much for learn.

    → Reply