Reversible Merge of Integer Hash Values Context:

I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's children. Additionally, I'd like to be able to replace one of the node's children in constant time (i.e., not doing a full recombination of hash values) as the branching factor for the tree could be quite large.

Question:

I am looking for a set of functions ($combine$, $separate$) that operate on fixed width integers and have the following properties.

Let $X$ be some set of integers with fixed width $b$.

(1) $combine(X)$ outputs an integer with width $b$

(2) $combine(X)$ operates in $O(|X|)$ time complexity

(3) $$combine\Bigl(\left\{t, separate\bigl(combine(X), x\bigr)\right\}\Bigr) = combine\Bigl(\bigl(X \setminus \{x\}\bigr) \cup \{t\}\Bigr)$$
where $x \in X$ and $t$ is some integer of width $b$.

(4) $separate(X, x)$ operates in $O(1)$ time complexity

(5) The outputs of $combine$ are going to be used as hash values so an algorithm with a "good" distribution of output values to avoid collisions is ideal. That said, I'd define good as anything better than trivial addition and subtraction (see below).

Initial thoughts:

A trivial implementation would have $combine$ and $separate$ be addition and subtraction (with some modulo logic); however, this obviously won't have a good distribution for tightly bunched input values.
A simple approach is to use the sum of hashes, e.g., 

$$\begin{align*}
\text{combine}(X) &amp;= \sum_{x \in X} H(x)\\
\text{separate}(y,x) &amp;= s - H(x)
\end{align*}$$

where $H(\cdot)$ is some good hash function.  To make the result suitable as a hash, I recommend that you hash the output of combine one more time before using it as a hash value.

More generally, you can use any commutative hash function.  See, e.g., https://crypto.stackexchange.com/q/6497/351 and https://crypto.stackexchange.com/q/11420/351 and https://crypto.stackexchange.com/q/54544/351 and Which fingerprinting/hashing algorithms support compounding?.

Another approach is to use a Merkle hash tree.  Store the list of children in a Merkle hash tree, one mini Merkle hash tree per node of your tree (i.e., a binary tree whose leaves are the children of the node, and where each internal node is augmented with the hash of the values in its two children, and the value in the root of hte Merkle tree is the hash of that node of your tree).  This allows $O(\lg n)$ updates rather than $O(1)$ updates, but that might be good enough.