My hashCode() is zero

Nov 1, 07:51 PM

If you’re curious, here is a larger list of strings that have a hashCode() of 0 in java. (compressed with 7zip)

Comment

---

Java hashCode() collisions

Oct 30, 11:26 PM

Having previously read about hash collision attacks, it occurred to me that it was not trivial to generate collisions.

In particular, I’m looking for strings that have a hashCode() of 0, since this can cause the JVM to re-compute the hash.

What do colliding alphanumeric Strings look like in java? Here’s a sample.

ARbyguv ARbygvW ARbygw8 ARbyhVv ARbyhWW ARbyhX8 ARbyi7v ARbyi8W ARbyi98 ARcZguv ARcZgvW ARcZgw8 ARcZhVv ARcZhWW ARcZhX8 ARcZi7v ARcZi8W ARcZi98 ASCyguv ASCygvW ASCygw8 ASCyhVv ASCyhWW ASCyhX8 ASCyi7v ASCyi8W ASCyi98 ASDZguv ASDZgvW ASDZgw8 ASDZhVv ASDZhWW

Comment

---

procedural geography

Apr 20, 10:08 AM

Amit Patel’s article on procedural map generation is a real gem.

It even includes a flash application for creating your own procedural maps.

In one article he manages to tie together:

It’s part of a larger body of useful game programming links he maintains on his site.

Comment

---

Swap distances between permutations

Apr 19, 02:36 PM

Given an ordered string T of unique elements, consider an operation that takes k elements and permutes them randomly.

If you consider all the permutations of T, and you categorize them according to the minimum number of operations required to reach T, how many permutations are in each grouping?

For example, ABC, where an operation is swapping 2 elements:
0 operations: ABC (1 permutation)
1 operation: BAC, CBA, ACB (3 permutations)
2 operations: CAB, BCA (2 permutations)

So we could write this as

Swap 2
  • n= 2: 1,3,2

So what do these groupings look like?

Swap 2
  • n= 2: 1,1
  • n= 3: 1,3,2
  • n= 4: 1,6,11,6
  • n= 5: 1,10,35,50,24
  • n= 6: 1,15,85,225,274,120
  • n= 7: 1,21,175,735,1624,1764,720
  • n= 8: 1,28,322,1960,6769,13132,13068,5040

h3.Swap 3

  • n= 3: 1,5
  • n= 4: 1,14,9
  • n= 5: 1,30,89
  • n= 6: 1,55,439,225
  • n= 7: 1,91,1519,3429
  • n= 8: 1,140,4214,24940,11025
  • n= 9: 1,204,10038,122156,230481

h3.Swap 4

  • n= 4: 1,23
  • n= 5: 1,75,44
  • n= 6: 1,190,529
  • n= 7: 1,406,4633
  • n= 8: 1,770,27341,12208
  • n= 9: 1,1338,118173,243368

Swap 5
  • n= 5: 1,119
  • n= 6: 1,454,265
  • n= 7: 1,1330,3709
  • n= 8: 1,3234,37085
  • n= 9: 1,6882,355997

Comment

---

Iterating over members of Stern-Brocot trees

Apr 18, 06:57 AM

Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first n rows of a Stern-Brocot tree.

It’s surprisingly simple. To generate the first n+1 rows, take the values

d8dd58c3ead2c31031724395b0e15d294759e777

where

5d856de78a34b77a3037d9971f7a93a1189dd7ac

given

76ecd9dbf7cfb3668daad2a8873e829b751fe5c5

where

d47008b4c68515aa8c9ad235d95af457b91db777

for odd j and non-negative vi.

Put informally, vi is the number of trailing zeroes in the binary representation of i.

What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.

Comment

---

« Older Newer »