<p>I need a hash-map-like structure that allows me to define custom equality. Do I have to write it myself? There should be a way to use custom hash and equality functions.</p>
<hr/>**评论：**<br/><br/>ericanderton: <pre><p>You may not need to write your own map implementation. It should be possible to write your own shallow or deep map comparison function for whatever map type you're using. The trick is to iterate the map keys, rather than use the built-in '==' operation, since Go's map implementation randomly hashes things such that two map instances are extremely unlikely to iterate in the same order.</p>
<p>The other route is to roll your own implementation. But beware: the only fully generic approach must wrap <code>map[interface{}]interface{}</code> since Go lacks compile-time generics. So the best practice here is to either roll a specific map wrapper, or again, just implement the comparison function(s) you need.</p>
<p>Edit: it <em>is</em> possible to create a type of the map you're interested in using, and write a receiver function for that type. IMO, this is as clean as it gets with Go:</p>
<p><a href="https://play.golang.org/p/gvvr6gGZON">https://play.golang.org/p/gvvr6gGZON</a></p>
<pre><code>type FooMap map[string]string
func(f FooMap) Equal(other FooMap) bool {
// todo: iterate key list and compare maps
return false
}
</code></pre></pre>golangguy: <pre><p>Sorry, to be clear I meant custom equality for the keys. Like overloading _ <em>eq</em> _ and _ <em>hash</em> _ in Python.</p></pre>ericanderton: <pre><p>I hear ya. Go, for better or worse, has <em>zero</em> operator overloading. </p>
<blockquote>
<p>You can't get there from here.</p>
</blockquote></pre>: <pre><p>[deleted]</p></pre>ericanderton: <pre><p>Was it this part?</p>
<blockquote>
<p>Go's map implementation randomly hashes things</p>
</blockquote>
<p>I can see how that might sound somewhat confusing. Plus, I mis-spoke, since I recall having to use map equality in some capacity in unit-tests, but I had a hard time getting it to work until I learned this odd Go behavior. As it happens, it's the iteration order of the map keys that's "random", not some property intrinsic to the maps themselves (like having some private RNG seed or somesuch).</p>
<p>This SO article sums up the overall problem much more succinctly: <a href="https://stackoverflow.com/questions/18208394/testing-equivalence-of-maps-golang" rel="nofollow">https://stackoverflow.com/questions/18208394/testing-equivalence-of-maps-golang</a></p></pre>FUZxxl: <pre><p>My comment is wrong and I feel wrong.</p></pre>jerf: <pre><p>"It depends". To be honest, almost every custom hash or equality function I've ever seen in the languages that permit it is doing something ill-considered in the context of a hash key, and I'm not sure Go doesn't generally have the right of it here.</p>
<p>It's also a bit of a code smell to have objects that complex as keys to a hash anyhow.</p>
<p>If you can do it, the best pure-Go way is to define a simpler object based on original value that can be unambiguously used as a hash key:</p>
<pre><code>type SomethingComplex struct { ... }
type SimpleKey struct { ... }
func (sc *SomethingComplex) Key () SimpleKey { }
</code></pre>
<p>and then define all maps using SimpleKey as the key type; the type system will not permit anyone to make the mistake of forgetting to convert.</p>
<p>If that isn't good enough, go poke around the ever-growing set of "go-generatable" data structures. I'm not sure you'll find one off-the-shelf but, if you understand the problem space well enough to understand <em>all</em> the invariants your custom functions need to maintain, you should be at the skill level where you could trivially add this feature to those data structures; it's a very simple and direct transform of any existing code.</p></pre>sunnyps: <pre><p>Maybe you can canonicalize your keys somehow. Say you wanted to use string keys but not be case sensitive, you could convert the key to a lowercase string before inserting it into the map and do the same when querying the map.</p></pre>atdiar: <pre><p>Yes, I think so. You can look at what is done in /runtime/alg.go for inspiration.</p>
<p>What is your intended use ? Toy project ?</p>
<p>edit: if it is for a toy project that will never ever.. ever... ever see production, I can help you as I've done this a while ago as a learning project of my own. I extracted a few files from the standard lib. But it was a toy project and there is some black magic of my own involved.</p>
<p>Otherwise, are you sure you really need a custom hashmap ?</p></pre>golangguy: <pre><p>It's very easy to code a production-ready hash map but it feels wrong when one is in the language already! It would be possible to extend maps to something like make(map[K]V, capacity, equalityFunc, hashFunc).</p></pre>atdiar: <pre><p>The default map/hash implementations are tied to the runtime, partly for additional protection against collisions and also, as far as I can recall, because the map is aware of the garbage collection process.
So, I don't think that your idea is possible. </p></pre>martingzz: <pre><p>I wrote this for my own needs:</p>
<p><a href="https://gitlab.com/mgmap/maps" rel="nofollow">https://gitlab.com/mgmap/maps</a></p>
<p>I mostly needed a map of something containing a slice as a part of the key which, and slices (as you probably know) don't support equality.</p>
<p>Let me know if it's any use to you.</p></pre>calebdoxsey: <pre><p>Just make your key have what you want in it:</p>
<pre><code>type (
User struct {
ID int64
Name, Email, Address string
}
UserKey struct{ ID int64 }
)
func (u User) Key() UserKey {
return UserKey{u.ID}
}
func main() {
m := map[UserKey]User{}
u1 := User{1, "name", "email", "address"}
m[u1.Key()] = u1
}
</code></pre>
<p>The only way I could see this not working is if you want to have a huge amount of data in your key, in which case you can transform that huge data into a single value (maybe sha256 it) and then use that as a key.</p>
<p>Given those two options, why would you ever need a custom function?</p></pre>golangguy: <pre><p>I have a huge amount of data. Using any hash as a key may collide with another value (I know for cryptographic hashes this is unlikely but still possible) and the computation of a cryptographic hash is slow.</p></pre>calebdoxsey: <pre><p>I don't think a map that allowed you to do this would actually solve your problem.</p>
<p>Say you are trying to store 1GB structs, the calculation of the hash (which a map is doing internally) will be quite expensive as will be the calculation of <code>equals</code> (which the map has to do on collision). But the whole point of a map is to give you O(1) lookups.</p>
<p>It would be better to pre-compute a key for each large object and store it with the object. This is, for example, how git works. Everything is stored as a sha1.</p>
<p>If you can't do that then you are using the wrong data structure. A hash map assumes hashing is efficient.</p></pre>jart1987: <pre><p>Why do you want to do this? What problem are you trying to solve?</p></pre>mcos: <pre><p>How about using <a href="http://golang.org/pkg/reflect/#DeepEqual" rel="nofollow">reflect.DeepEqual</a>?</p></pre>hipone: <pre><p>You shouldn't write your own hash-map, you should revisit your requirements. In particular, why builtin map is not enough for you?</p>
<p>([edit] it's pretty obvious that there exist no such thing as "custom equality" as equality is only one in Go - byte-wise one, so I smell troll; if yes, please see my counter-troll: <a href="https://play.golang.org/p/UM6aJlM28D" rel="nofollow">https://play.golang.org/p/UM6aJlM28D</a>)</p></pre>golangguy: <pre><p>I am aware that Go equality mentioned in the spec is pretty much binary equals. Although from what I can tell for interfaces this isn't quite the case. See my message above for clarification.</p></pre>dchapes: <pre><p>Tiny nits for your example: you should probably either use your own <code>const HashSize = sha1.Size</code> (or just use <code>sha1.Size</code> directly) everywhere in place of <code>20</code>. There is no reason to use pointer receivers for the <code>Map</code> methods.</p></pre>
