The idea is that this is used to suggest whether when rendering a component, the children are new components, or simply existing components with updated props.
E.g. You have a component that renders a list of items. If you add an item, what you would rather do is create a single new child component and re-use the previously generated children vs. discarding the child components from a the previous render and creating a brand new set.
If you create a key based on a hash of the props this will decrease the time taken to re-render an set of child components with identical props, but at the cost of discarding an existing component and creating a new one if one of the props changes.
Or something like that.....
See for a bit more detail: https://facebook.github.io/react/docs/reconciliation.html
I'll assume your key is quick to calculate. If a prop change causes the hash / key to change then react doesn't know how to reuse the dom fragment. I guess it will just reuse the stuff that's in the same location in that case so maybe it's fine. You'll lose the advantage that keys give you in the first case which is dealing with reordering.
And actually, just because the key changes or not, that doesn't cause a rerender or not. The rerender is always going to happen. Right? Unless I'm missing something.