AVL Tree or HashTable for storing relatively big data?
For search dominant operation, supported insert, delete, find only there are huge benefits in using the Hash Table.


the memory footprint is low, only colliding entries require pointer, one per entry while AVL requires two pointers per entry.
access time is expected $\mathcal O(1)$, say in the worst case 5, which gives one hash calculation and 5 equality tests while AVL has 25 full comparissons for 120000 entries in the worst case.
rehashing could be avoided with maximal capacity known in advance, otherwise it would be rare operation.


What would opt for AVL?


traversal queries, looking for ranges etc.
access to sorted data.
inexact queries, looking for nearest neighbour (at the cost of additional pointers).


By the way the perfect hash table is commonly refered to as having no collisions, which requires static setting, rehashing. What you refer to is probably dynamic perfect hashing, a two-tier scheme with guaranteed deterministic constant lookup.

If you have all data (or substantial amount) it is beneficial to sort data and create balanced tree to avoid inserting nodes one by one. (Something like DSW algorithm would help).
In that case the hash table may be constructed without collisions at all for initial data, leaving space for future elements and work really fast.

For the search part, none of the structures would help. If I understood correctly, your data is a graph, so both presented structures will help with indexing only and the Hash Table is the winner.

Sidenote:
To store compactly textual data something like Trie or Directed Acyclic Word Graph would be better. The edited part about search would require a graph, path finding algorithm and auxiliary indexing data structure, in your case probably Hash Table or DAWG used as map.