Is there a simple way to convert a unique string of characters into a unique number in JavaScript?

Question

This is nearly a cross post from Math SE - while the explanation of my problem is identical, on Math.SE I was asking for a mathematical solution to my problem.

My issue is, the solution I got on Math.SE was "convert to base 35" which is probably a very good answer, but I am truly horrible with math and don't understand how to apply the solution in my code. I tried looking up a lesson on converting to different bases, and it's pretty confusing to me. Even looking at a question about converting numbers to bases in JavaScript didn't make it clear how exactly I'd use it for what I need to do.

Is there a simple way to handle this in JavaScript? Here's the question in full:

I have an unusual programming problem and the math side of it has me stumped.

I've generated a unique string of seven characters which are each randomly selected from these possibilities: ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789 for example A6HJ92B and I need to convert it to a unique number value. When converted, no two versions of this random string can be the name number.

I could just generate a number rather than including letters in the original id, but of course that means I have to increase the length of my string, and it's possible that the user of my application may want to type this string, as it identifies his "session" in an application, so I want to keep it short.

So my idea was to build a table like this:

A : 1,
B : 2,
C : 3,
D : 4,
E : 5,
F : 6,
G : 7,
H : 8,

... you get the idea ...

5 : 31,
6 : 32,
7 : 33,
8 : 34,
9 : 35

And then I'd add all of the numbers up...

A6HJ92B:

A : 1
6 : 32
H : 8
J : 10
9 : 35
2 : 28
B : 2

1+32+8+10+35+28+2 = 116

...but I realized this is a flawed idea because many possible strings will "collide" or equal the same number. I need each unique string to equal a unique number.

So even if I multiplied each character's value (1*32*8*10*35*28*2 = 5,017,600), I'm thinking there might be possible collisions there too.

Is there a way to calculate this in a way that eliminates collisions? If the collisions cant be eliminated, what methods can I use to minimize them?

Answer 1

Basically, you want an injective transformation f : S → N, where S is the set of JS strings of length 7 with characters A-Z1-9, and N is the set of all JS numbers.

A possible approach is considering that the strings in S are a positional encoding of numbers, as you attempted.

However, in order to be injective (avoid collisions), you should multiply the value of each character by the basis to the power of the position.

For example, given the following table of character values

0 ⟶  0
1 ⟶  1
⋮      ⋮
9 ⟶  9
A ⟶ 10
B ⟶ 11
⋮      ⋮
Z ⟶ 35

A6HJ92B would become 10×36⁶ + 6×36⁵ + 17×36⁴ + 19×36³ + 9×36² + 2×36 + 11, that is, 22160072099.

You can do the conversion easily with parseInt and toString:

parseInt('A6HJ92B', 36); // 22160072099
(22160072099).toString(36).toUpperCase(); // "A6HJ92B"

If you want to use an arbitrary table of values, you will have to code the transformations manually.

Note that in JS, numbers are double-precision floats of 64 bits. That means there is a finite precision, and you can't store arbitrarily big integers. It won't work properly beyond this maximum

Number.MAX_SAFE_INTEGER; // 9007199254740991
Number.MAX_SAFE_INTEGER.toString(36).toUpperCase(); // "2GOSA7PA2GV"

But since your strings only have 7 characters, it should be enough.

Answer 2

Essentially what you want is the equivalent of Java's hashcode. This is the formula used in Java: where n is the total length of the string, and s[i] is the ith character of the string. Basically what you're doing is:

For each character in the string, multiply it by 31 raised to the power of the difference between the total length of the string and the index of the current character in the string minus 1.

Answer 3

You're just not thinking about the problem the right way. Let's start with something you are more familiar with; decimal, or base 10 numbers.

The number 7158 is composed of:

  7 x 10 ^ 3
 +1 x 10 ^ 2
 +5 x 10 ^ 1
 +8 x 10 ^ 0

To represent the number in base X you replace the 10 with X.

So now the question becomes how to convert between bases. The simplest solution is to divide by X repeatedly - each time convert the remainder to base X and add it to the front of your output string until there's nothing left, then use the integer part of the division for the next iteration:

7158 /35 = 204 remainder 18
204 / 35 = 5 remainder 29
5 / 35 = 0 remainder 5

So in base 35, the decimal number 7158 is represented by the symbols you choose for [5][29][18]

If you try the example above yourself by multiplying the fractional part of each division by 35 you may get some results which are not integers - computers work in binary (and are automatically doing the base conversion) and only work with a fixed number of digits - I.e. depending on how you do the calculation you may need to round of by around 0.00001 to get the remainder as an integer.

Answer 4

You could multiply by the position power:

function StringAdder(obj){
  this.vals = obj;
  this.add = function(str){
    var s = str.split(''), l = s.length, p = Math.pow(10, (l-1)), r = 0;
    for(var i=0; i<l; i++){
      r += this.vals[s[i]]*p; p = p/10;
    }
    return r;
  }
}
var vals = {
  A: 1,
  6: 32,
  H: 8,
  J: 10,
  9: 35,
  2: 28,
  B: 2
}
var sa = new StringAdder(vals);
console.log(sa.add('A6HJ92B')); console.log(sa.add('HJA6B29'));