Win a copy of Testing JavaScript Applications this week in the HTML Pages with CSS and JavaScript forum!

John Vorwald

Ranch Hand
+ Follow
since Sep 26, 2010
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
1
Received in last 30 days
0
Total given
9
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by John Vorwald

With enough "points" / lines, the code could run out of memory in mouseDragged. You may need to limit the number of points / lines to be added, or increase the amount of JVM memory available.
7 years ago
Alan,
You have to be more specific about why your code and algorithm doesn't work.
Since you are not getting the "sorted" array results that you want, one place to be more specific is where the sorting is done in your algorithm.
Also, once you have some sorting in your code, you will have to be able to add a new student anywhere in the list, not just at the end.

The following code is where the student array is created and the new student is added.
When you create the array, it appears that you know the maximum number of students to add.
Some questions about this code:
1) When you add a student, you are currently adding the student at location "numOfStudents". What is the value of "numOfStudents on the first call to addStudent?
2) How do you know that location where you are adding a student is the "right" location?
3) What needs to occur when you need to add a student somewhere besides the end?

Can you write "tests" to check the above questions? Then work on the code till all the tests are satisfied. Also, you could add some print statement to the add function to print the location that is being added, and the items currently at that location and the prior location and the next location so you can see where the code is adding the student.



7 years ago
How can I log messages from different threads into different files. Can I do this using log4j?

Never mind, I used this example and will sort the output.
7 years ago

Jeff Verdegan wrote:

Stuart A. Burkett wrote:You can't.


John Vorwald wrote:You could use the ordinal method.



That depends on whether the OP is talking about an Enumeration or an Enum (enum). Given that he said "Enumeration" and is asking about the "previous element," my money is on Enumeration.



Appears I need to read the question more carefully.... in order to avoid the dreaded "mouth in gear before brain is engaged" syndrome
7 years ago
Let's see

Enumeration: a predefined interface that tests for more elements and accesses the next element.

And the question is can Enumeration have previousElement();

Is it satisfactory to extend Enumeration? i.e.



Maybe something like


produces output
7 years ago
Try to set up a MVC construction first, and get data to pass from the view to the models, and messages from the models to the views, via the controller. The approach that I used was to declare the controller(s) in main, and pass the controller(s) to the views / models constructors. Also, register the views / models inside the controller so the controller can call all the models / views. Then the views / models can call the controller and vice versa. Also, you can set a property and use the property name to create a method name, ie set_+propertyName. Then check the views and models for the existence of that method, and call the method appropriately. But, there is probably an easier way to do this using messages.... Be careful about multi thread access too.
7 years ago
You could use the ordinal method.

7 years ago
The original question was about different strings that had the same hash code. I sat in a facial recognition meeting last week, and part of the meeting dealt with patterns that were used to create binary scores to quickly locate the face and/or facial features in a digital photo. I wonder if that approach could be applied to the problem of finding different strings that have the same hash code. My simple understanding of the approach was to try a pattern on a number of test cases, and if the pattern had better than 51% chance of success (or failure in which the criteria was reversed), then the pattern could be used. Just a thought, the program isn't obvious to me, so maybe another day....
7 years ago
Mike,
That's an interesting response. I'm going to see if I can take it a little further, but include some code due to the details... It looks like 7 characters are needed to cover the full range.

John



7 years ago

drac yang wrote:

John Vorwald wrote:It may be worth pointing out that since the hash code is an int, and there are 4294967295 values for int, all possible hash codes can be generated with a seven character string.



if it's only for alphabets, seven character string could represent totally 26^7 = 8031810176 which is bigger than all the int number 2^32 = 4294967296

it might be sufficient though, it's possible to find two different strings with the same hashcode.



The question refers to String hash codes, which are given by sum((int)(char[i]) * 31^(nChar-i)) with mod applied when the value exceeds Integer max value.

If we use the printable ascii char, the values range from 32 to 127

We see that 127 * 31^(6-1) = 3607273026, which is less than 4294967296. There needs to be a 7th char to get the required amount of hash values.

The number of hash codes doesn't depend on 26^nchar, but rather (int(char)*31^(nchar-1)). The 26^nchar is the number of possible arrangements of single case (lower or upper) words, but not the number unique hash values.

7 years ago
It may be worth pointing out that since the hash code is an int, and there are 4294967295 values for int, all possible hash codes can be generated with a seven character string.
7 years ago
Since the hash value of a string is given by
h(i+1) = h(i)*31 + (int)str[i];

This expands to
h = ((int)str[0])*31^(length(str)-1) + ((int)str[1])*31^(length(str)-2) + ((int)str[2])*31^(length(str)-3) + ((int)str[i])*31^(length(str)-(i+1)) ... ((int)str[length(str)-2])*31) + (int)str[length(str)-1]

One approach to generating a second string with the same hash value is to modify the characters so that the same value comes up. If we limit the range of characters to the ASCII set, then this means that the second to last character can be changed by up to three values (i) and the last character changed by -i*31.

A second way that two different strings can generate the same hash is to use the range of int which is from -2,147,483,648 and 2,147,483,647 inclusive.. Since 31^7 = 27,512,614,111, this suggests that the hash value of a string with more than 6 characters would exceed the range of an int, causing folding, and providing a second methodology for matching the hash values of two different strings. If we add one to the maximum integer, we obtain the minimum integer. This suggests that the hash value is given by

ht = h(i)*31 + (int)str[i];
while (ht > 2147483647) ht = ht - 4294967295
h(i+1) = ht

Note that 4294967295 = 4*31^6 + 26*31^5 + 19*31^3 + 29*31^2 + 24*31 + 3

So, that suggests that if we start with a string with more than six characters and shift the seventh character from the end by 4, and the sixth character from the end by 26 and the fourth character from the end by 19 and the third character from the end by 29 and the second character from the end by 24 and the last character by 3, we should obtain a different string with the same hash value. Actually, the last character has to be shifted by 4.

The code below generates both types of string modifications to obtain new strings with the same hash code. The integer folding could be repeated to create additional different strings. The integer folding approach was not checked for generating only ASCII characters, so the printed characters may be misleading.



Output

7 years ago
It is difficult to wade through code to determine the cause of a bug. You can try to break the process into smaller pieces, identifying states that cause or characterize the bug, determining how these states are modified, isolating the code that modifies the states, determine what the correct states should be to mitigate the bug.

I will mention that I've been programming for more than 30 yrs, and recently had a bug I never saw before, and had a HARD time isolating the bug (which was an unexpected recursive call through toString members). It took a few days to identify what part of the code was even associated with the bug.
7 years ago
Below is an example code to generate strings with matching hash codes.

7 years ago
The char variable has a range of 65535 values

The hash value of a string is given by
h(i+1) = h(i)*31 + (int)str[i];

Since 31 is less than 65535, there are a multitude of strings that have the same hash value.

Example, for a four character string, h = 29791 * (int)str[0] + 961* (int)str[1] + 31* (int)str[2] + (int)str[3]

So, a matching hash is given by making trivial changes. For example, increase str[2] by one, and decrease str[3] by 31

hash("abyz") = 2987778
hash("abz]") = 2987778



If the hash multiplier, 31, was larger than 65535, then there would be no values that generate the same hash.

In general, since the ascii codes range from 33 to 175, or 142 values, you could shift the next to last character by up to 3 places up or down, and adjust the last character to generate the same hash. If you use non ascii codes, or the full 65535 values, you could adjust the last four characters and obtain different strings that generate the same hash code.
7 years ago