How is the similarity of the structure of two functions defined?

Consider the sets $X=\{1,2,4\}$ and $Y=\{A,B,C\}$ and then consider two functions $f:X\to X$ and $g:Y\to Y$ defined as $f=\{(1,4),(2,1),(4,1)\}$ and $g=\{(A,C),(B,A),(C,A)\}$. Certainly, these function have the same "structure", but what is it? What makes this functions more or less equal?

What I've noticed is that there exists a function $h:X\to Y$ such that $f=h^{-1}\circ g\circ h$. Must this hold for any two functions to have the same "structure"? What property does this make $f$ and $g$ have?

Note that $h$ is a bijection. We say that $f$ and $g$ are conjugate maps. This notion is very useful in linear algebra and dynamical systems for instance, to reduce maps to simpler forms.

You are correct - you can construct two composite functions $h \circ f:A \to B$ and $g \circ h:A \to B$ such that $(h \circ f)(x) = (g \circ h) (x) \quad \forall x \in A$. In other words $h \circ f = g \circ h$.

You could say that functions $f$ and $g$ are isomorphic. In category theory terms, $f, g$ and $h$ form a commutative diagram.