{"id":9193,"date":"2011-11-04T07:00:00","date_gmt":"2011-11-04T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/11\/04\/how-do-i-generate-a-unique-32-bit-value-for-a-time-zone\/"},"modified":"2011-11-04T07:00:00","modified_gmt":"2011-11-04T07:00:00","slug":"how-do-i-generate-a-unique-32-bit-value-for-a-time-zone","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20111104-00\/?p=9193","title":{"rendered":"How do I generate a unique 32-bit value for a time zone?"},"content":{"rendered":"

\nPublic Service Announcement:\nDaylight Saving Time ends in most parts of the United States this weekend.\n\nOther parts of the world may change on a different day from the\nUnited States<\/a>.\n<\/p>\n

\nA customer asked the following question:\n<\/p>\n

\nGiven two\nTIME_ZONE_INFORMATION<\/code> structures,\nI would like to compute a LONG<\/code> for each\nthat I can then compare to determine whether they represent\nthe same time zone.\n When I say the same, I mean that when the two are passed\nto System­Time­To­Tz­Specific­Local­Time<\/code>\nwith the same LPSYSTEM­TIME<\/code> input, the output is the same.\n<\/p><\/blockquote>\n

\nA TIME_ZONE_INFORMATION<\/code> structure\ncontains more information than can be packed into a 32-bit value.\n(At least there’s no obvious way to pack it into a 32-bit value.)\nYou’re not going to be able to squeeze the entire structure\ninto a 32-bit value that is unique for each time zone,\nso that comparing the 32-bit values will tell you whether the\ntime zones are the same or not.\n<\/p>\n

\nFortunately, the customer also provided context for the\nquestion, explaining their underlying problem.\nAnd as is often the case, the customer had broken down the\nproblem into two parts, one easy and one impossible.\nThe customer solved the easy part\nand was asking for help with the impossible part.\n<\/p>\n

\nBut on closer inspection, the problem wasn’t so much impossible\nas it was improperly specified:\n<\/p>\n

\nThe bigger problem I’m actually trying to solve is that we call\nSystem­Time­To­Tz­Specific­Local­Time<\/code>\ninside a deeply\nnested loop.\nI would like to cache the results for performance,\nusing the time zone as a key to a CAtl­Map<\/code>\nwhich would hold the cached results for each time zone.\nI’m looking for help coming up with what combinaion of the\nstructure members to use to uniquely identify the time zone.\n<\/p><\/blockquote>\n

\nOkay,\nthe customer appears to be a bit confused about hash keys.\nHash keys do not need to be unique for each time zone.\nIt is perfectly legitimate for two different items to result\nin the same hash value;\nthat’s why we have the term hash collision<\/i>.\nOf course, you want to take reasonable steps to minimize collisions,\nbut when you don’t control the domain space,\nhash collisions are a part of life.\n<\/p>\n

\n

\nFrom looking at some time zone data, it looks like\n(Bias + Standard­Bias)<\/code> is unique for any time zone,\nbut I know that there are a lot of complicated\nissues when dealing with time zones\nso I wanted to check if I could be sure of that.\n<\/p>\n

\nLONG CTimeZoneTraits::GetHash(const TIME_ZONE_INFORMATION& tz)\n{\n return tz.Bias + tz.StandardBias;\n}\nint CTimeZoneTraits::Equals(const TIME_ZONE_INFORMATION& tz1,\n                            const TIME_ZONE_INFORMATION& tz2)\n{\n return tz1.Bias         == tz2.Bias &&\n        tz1.StandardBias == tz2.StandardBias &&\n        tz1.DaylightBias == tz2.DaylightBias &&\n        memcmp(&tz1.StandardDate, &tz2.StandardDate,\n                                  sizeof(tz1.StandardDate) &&\n        memcmp(&tz1.DaylightDate, &tz2.DaylightDate,\n                                  sizeof(tz1.DaylightDate);\n}\n<\/pre>\n<\/blockquote>\n
\nIf you think it about it, it’s clear that\n(Bias + Standard­Bias)<\/code> does not always uniquely identify\na time zone.\nConsider two cities at the same longitude in the same hemisphere\nin the middle of winter:\nThey will have the same Standard­Bias<\/code>\n(because they have the same longitude) and the same\nBias<\/code>\n(because Daylight Saving Time is not applicable during the winter),\nbut if the cities are in different countries (or sometimes,\neven\n\ndifferent parts of the same country<\/a>),\nthey will transition to\/from Daylight Saving Time differently\nand consequently do not belong to the same time zone.\n<\/p>\n
\nOn the other hand, since this is being used simply as a hash key,\nuniqueness is not an absolute requirement,\nso even a bad hash function will still “work”;\nit’ll just be slower than a good hash function.\n<\/p>\n
\nIf it were up to me, I would choose as a hash function\nsomething like this:\n<\/p>\n
\nLONG CTimeZoneTraits::GetHash(const TIME_ZONE_INFORMATION& tz)\n{\n return tz.StandardBias +\n        tz.StandardDate.wDay +\n        (tz.StandardDate.wDayOfWeek << 16) +\n        (tz.StandardDate.wMonth << 24);\n}\n<\/pre>\n
\nI wouldn’t use the Bias<\/code> in the hash code because\nthe Bias<\/code> changes over time.\nIf the hash table lifetime extends across a daylight saving time transition,\nthen the Bias<\/code> will change.\n<\/p>\n
\nFor the hash, I use the Standard­Bias<\/code>, which is the number\nof minutes east of UTC.\nIn practice this does not exceed\n60 × 25 = 1500,\nand it’s a multiple of 30.\n(But\n\nnot necessarily a multiple of 60<\/a>.)\nThe wDay<\/code> is typically in the range [0,5], though it can\ngo as high as 31 if the transition is based on a specific day.\nTherefore, I’ll simply add it to the Standard­Bias<\/code>,\ntaking advantage of the fact that the Standard­Bias<\/code> is\na multiple of 30.\nThe month and day of the week are thrown into the upper 16 bits.\n<\/p>\n
\nNow, this hash function will still have collisions: If there are\ntwo time zones at the same longitude\nwhich transition to Standard time with the same rule,\nbut which transition to Daylight time according to different rules,\nthen we will still have a collision.\n<\/p>\n
\nI would like to reduce the number of collisions\nby understanding how often two equal values of\n(Bias + Standard­Bias)<\/code>\ncould represent different time zones.\n<\/p><\/blockquote>\n
\nHow likely is such a collision?\nYou can answer this question yourself:\nTake all the time zones currently known to the system and\nhash them all to see what happens.\nOf course,\n\ntime zones change all the time<\/a>,\nso don’t assume that\nyour results will hold true in perpetuity,\nbut if you’re just looking for a rough guide, calculating\nagainst the current state of affairs is a pretty good one.\nIt’s true that time zones change all the time,\nbut they typically don’t change by much.<\/p>\n","protected":false},"excerpt":{"rendered":"
Public Service Announcement: Daylight Saving Time ends in most parts of the United States this weekend. Other parts of the world may change on a different day from the United States. A customer asked the following question: Given two TIME_ZONE_INFORMATION structures, I would like to compute a LONG for each that I can then compare […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25,108],"class_list":["post-9193","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code","tag-time"],"acf":[],"blog_post_summary":"
Public Service Announcement: Daylight Saving Time ends in most parts of the United States this weekend. Other parts of the world may change on a different day from the United States. A customer asked the following question: Given two TIME_ZONE_INFORMATION structures, I would like to compute a LONG for each that I can then compare […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/9193","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=9193"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/9193\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=9193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=9193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=9193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}