Use itertools.count:

from itertools import count

class MyClass(object):
    id_counter = count().next
    def __init__(self):
        self.id = self.id_counter()

Perhaps uuid.uuid4() might do the job. See uuid for more information.

Use uuid:

import uuid
uuid.uuid4()

results in things like:

UUID('35ad767c-da61-4731-adbc-cdd96efac2c4')

And a link to the python docs: https://docs.python.org/3.5/library/uuid.html

This is some nice-looking Python code. Good work. Though, if you were to run pylint over this, you'd still find:

************* Module cr
cr.py:1:0: C0114: Missing module docstring (missing-module-docstring)
cr.py:44:12: W0612: Unused variable 'i' (unused-variable)

------------------------------------------------------------------
Your code has been rated at 9.20/10

So, it's usually good practice to add a module docstring at the beginning of the module. I've seen many people adding the same docstring as the one for the class within that module (if it's just one).

From PEP8:

All modules should normally have docstrings, and all functions and classes exported by a module should also have docstrings. Public methods (including the __init__ constructor) should also have docstrings. A package may be documented in the module docstring of the __init__.py file in the package directory.

So, in the end, it is just a matter of preference.

You also have a magic number: 1000000. I'd just take it out of your __init__ and define it as a constant. Something like:

MAX_RANGE = 1000000

Now, the second pylint warning tells you that here:

for i in range(0, n_ids):  # you're not using i at all
    random_ids.append(self.random())
return random_id

So you could just replace it with _:

for _ in range(0, n_ids):
    random_ids.append(self.random())
return random_id

Even better, you could entirely rewrite the above and use a list comprehension instead:

def randoms(self, n_ids: int):
    """
    Generate list of random ids
    :param n_ids: number of id you need to generate
    :return: list of random ids it might contains duplications
    """

    return [self.random() for _ in range(0, n_ids)]

The same applies for get_unique_ids() method (although some might argue that there's a small benefit in favour of readability):

def get_unique_ids(self):
    """
    :return: list of unique ids it randomize from
    """

    return [
        hashlib.md5(str(i).encode()).hexdigest()
        for i in range(self.__start_num, self.__end_num + 1)
    ]

From this SO answer:

List comprehension is basically just a "syntactic sugar" for the regular for loop. In this case the reason that it performs better is because it doesn't need to load the append attribute of the list and call it as a function at each iteration. In other words and in general, list comprehensions perform faster because suspending and resuming a function's frame, or multiple functions in other cases, is slower than creating a list on demand.

This won't have such a big impact on the actual speed, but it's definitely giving you a nice start :)

Another advice would be to use Numpy if you want to generate large numbers of random ints; if you're just generating one-at-a-time, it may not be as useful (but then how much do you care about performance, really?).

Libraries like Numpy carefully move as much compute as possible to underlying C code.

Every number from 1,2,5,6,9,10... is divisible by 4 with remainder 1 or 2.

>>> ','.join(str(i) for i in xrange(100) if i % 4 in (1,2))
'1,2,5,6,9,10,13,14,...'