Hash Collision - what are the chances?

Question

How can you show Google Maps InfoWindows OnLoad of the document? Everything works perfect. The InfoWindow pops up on click but I am not 100% sure how to solve the problem, that it shows up on load...

Please find my code below:

    <script type="text/javascript">
        var infowindow = null;

        $(document).ready(function() {
            initialize();
        });

        function initialize() {
            var centerMap = new google.maps.LatLng(52, 10);

            var myOptions = {
                zoom: 5,
                center: centerMap,
                scrollwheel: false,
                mapTypeId: google.maps.MapTypeId.ROADMAP
            }

            var map = new google.maps.Map(document.getElementById("maps"), myOptions);

            setMarkers(map, sites);
            infowindow = new google.maps.InfoWindow({
                content: "loading...",
                maxWidth: 60
            });

            var bikeLayer = new google.maps.BicyclingLayer();
            bikeLayer.setMap(map);
        }

        var sites = [
            // array here
        ];

        function setMarkers(map, markers) {
            for (var i = 0; i < markers.length; i++) {
                var sites = markers[i];
                var siteLatLng = new google.maps.LatLng(sites[1], sites[2]);
                var marker = new google.maps.Marker({
                    position: siteLatLng,
                    map: map,
                    title: sites[0],
                    zIndex: sites[3],
                    html: sites[4]
                });

                var contentString = "Google Maps";

                google.maps.event.addListener(marker, "click", function () {
                    infowindow.setContent(this.html);
                    infowindow.open(map, this);
                });
            }
        }
    </script>

Solution 1

If you assume that SHA-1 does a good job, you can conclude that there's a 1 in 2^160 chance that two given messages have the same hash (since SHA-1 produces a 160-bit hash).

2^160 is a ridiculously large number. It's roughly 10^48. Even if you have a million entries in your database, that's still a 1 in 10^42 chance that a new entry will share the same hash.

SHA-1 has proved to be fairly good, so I don't think you need to worry about collisions at all.

As a side note, use PHP's raw_output feature when you use SHA-1 as this will lead to a shorter string and hence will make your database operations a bit faster.

EDIT: To address the birthday paradox, a database with 10^18 (a million million million) entries has a chance of about 1 in 0.0000000000003 of a collision. Really not worth worrying about.

Solution 2

Use a symmetric encryption scheme and a private server key to encrypt the ID (and other values) when you send them to the client and decrypt again on reception. Take care that your cryptographic function provides both confidentiality and integrity checks.

This allows you to use sensible values when talking to the DB without any collision, great security when talking to the client and reduces your probability to land on thedailyWTF by approximatly 2^160.

See also Pounding A Nail: Old Shoe or Glass Bottle?!

Solution 3

why not do something which guarantees there'll be no collisions, as well as makes sure that no one can change a GET parameter to view something they shouldn't: using a salt, combine the id and its hash.

$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5

even if you do accidentally stumble upon two numbers which have the exact same sha1 hash (with your salt), then the $key will still be different and you'll avoid all collisions.

Solution 4

If you use numerically increasing IDs as input, then chances are practically zero that SHA-1 will collide.

If the ID is the only input, then SHA-1 seems to be quite some overkill - producing a 160 bit hash from a 32-bit integer. I would rather use modular exponentiation, e.g. chose a large (32-bit) prime p, compute the modular generator g of that group, and then use g^id. This will be guaranteed collision free, and only give 32-bit "hashes".

Solution 5

From first principles:

SHA-1 produces a 160-bit digest. Assuming it uses the entire bit-space evenly (which is presumably what it was designed to do), that is only a 2^-160 chance on each insert that you would get a collision.

So for each insert, it should be safe to assume there is no collision, and deal with the error if there is.

That is not to say that you can ignore the chance of collision entirely.

The Birthday Paradox suggests the chance of there being at least one collision in your database is higher than you would guess, because of the O(N^2) possible collisions.

View more solutions

Comments

[HoangHieu]

trigger marker click :3

[HoangHieu]

flow answer stackoverflow.com/questions/28497023/…

[brenzy]

Call infowindow.open to open the infowindow while loading, and the close it when you are done.

[Maxi]

Can anybody please provide an working example for the code above?

[geocodezip]

Which infowindow did you want opened on load?

[Maxi]

Sorry but the "same kind of discussion" is about an onclick event not onload.

[Maxi]

I'm failing the whole time, even with your example. How and where do I have to to put it into my code :(

[Meroshini]

Yes. To add a method to your onload function, you can try this infoWindow = new google.maps.InfoWindow(); google.maps.event.addListener(infoWindow, 'DOMContentLoaded', function() { // Here call InfoWindow.open() method });

[Maxi]

But how can I adjust it to the piece of code I have? I don't see how I can solve it...

[Maxi]

Thanks, but how can I make "marker" global if it's only called in the SetMarker function?

[Maxi]

I don't see how you show how I can make my setMarker function "marker" variable global... your onload script tells me undefined marker, of course.. :(

[Maxi]

Can you please have a look at my code and show me what to do? I understand your way of solving it, but I do not understand how to re-develop my construction

[Maxi]

Yes, all windows on load :(

[HoangHieu]

you have array of markers, just for all it and trigger event to a marker :3

[Maxi]

Can you please just show me how? I browsed the web for 2 days, already tried all snippets, adjusted everything... "just trigger" sounds easier as it is

[Maxi]

I don't understand what to do? Can you not just copy and paste my snippet and show me where to put your snippet?

[Maxi]

it says here: _markers[] = new google.maps.Marker({ Uncaught SyntaxError: Unexpected token ]

[HoangHieu]

ah sorry about that. change to _markers[i] = new google.maps.Marker... it will work :)